How is House Robber II different from House Robber?

The houses form a circle, so the first and last houses are neighbours and cannot both be robbed. Everything else — no two adjacent houses, maximise the total — is the same.

Why does running House Robber twice work?

Any valid plan leaves out the first house or the last house (or both). Plans that leave out the last house are exactly the plans for the straight street 0..n-2; plans that leave out the first are the plans for 1..n-1. The best overall is the better of the two straight-street answers.

What happens with only one house?

Return it. Both ranges 0..n-2 and 1..n-1 would be empty, so the single house is handled before the two passes.

House Robber II

Rob houses arranged in a circle, where the first and last are neighbours, by running House Robber twice on two straight streets.

MediumSolve on LeetCode

Problem Understanding

House Robber II: houses hold nums[i] money each and stand in a circle, so the first and last houses are neighbours. Robbing two adjacent houses sets off an alarm. Return the most money you can rob.

Example: [2, 3, 2] returns 3. Houses 0 and 2 are neighbours here, so 2 + 2 is not allowed.

Attempt 1: Patch House Robber

House Robber solves a straight street. Running it unchanged on the circle can rob both ends: on [2, 7, 9, 3, 1] it robs houses 0, 2 and 4 for 12, but houses 0 and 4 are neighbours. Trying to repair that inside one pass means tracking whether house 0 was robbed through every state — workable, but easy to get wrong. There is a simpler split.

The Intuition: Break the Circle in Two Ways

The only new constraint is between house 0 and house n − 1: at most one of them is robbed. So every valid plan falls into at least one of two cases:

House n − 1 is not robbed. Then the circle is just the straight street 0..n−2.
House 0 is not robbed. Then it is the straight street 1..n−1.

Run House Robber on each street and return the larger total. Each pass keeps only two values — prev2 and prev1, the best totals ending two houses back and one house back — so the extra space is O(1). A single house has no neighbour at all and is returned directly.

Interactive Walkthrough

A CIRCLE: FIRST AND LAST ARE NEIGHBOURS

SPLIT THE CIRCLE

houses

↔ last

↔ first

prev2

—

prev1

—

A: 0..3

—

B: 1..4

—

Answer

—

Houses 0 and 4 are neighbours in the circle, so at most one of them is robbed. Solve two straight streets: without house 4, then without house 0

Street A: houses 0..3 (house 4 left out). prev2 = prev1 = 0

Houses

The circle is drawn as a row whose two ends are neighbours. Street A greys out the last house and Street B the first; within each pass, the house being decided is robbed or skipped and prev2/prev1 update. The two totals sit side by side until the larger is returned.

Dry Run Table

Input: [2, 7, 9, 3, 1]

Street	House (value)	Skip `prev1`	Rob `prev2 + value`	Best so far
A (0..3)	0 (2)	0	0 + 2 = 2	2
A	1 (7)	2	0 + 7 = 7	7
A	2 (9)	7	2 + 9 = 11	11
A	3 (3)	11	7 + 3 = 10	11
B (1..4)	1 (7)	0	0 + 7 = 7	7
B	2 (9)	7	0 + 9 = 9	9
B	3 (3)	9	7 + 3 = 10	10
B	4 (1)	10	9 + 1 = 10	10

Return max(11, 10) = 11 — less than the straight street's 12, because that plan robbed both neighbouring ends.

The Solution Template

House Robber's two-variable loop as a helper, called on two ranges.

House Robber II Code

1var rob = function(nums) {
2    if (nums.length === 1) {
3        return nums[0];
4    }
5    const n = nums.length;
6    return Math.max(line(nums, 0, n - 2), line(nums, 1, n - 1));
7};
8
9function line(nums, lo, hi) {
10    let prev2 = 0, prev1 = 0;
11    for (let i = lo; i <= hi; i++) {
12        const best = Math.max(prev1, prev2 + nums[i]);
13        prev2 = prev1;
14        prev1 = best;
15    }
16    return prev1;
17}

Edge Cases & Common Mistakes

One house: return it; both ranges would be empty.
Two houses: each range holds one house, so the answer is the larger of the two.
Running House Robber once on the whole circle: it can rob both ends — [2, 7, 9, 3, 1] would give 12 instead of 11.
Excluding both ends in one pass: valid but not enough; the best plan may need one of the ends, as in [1, 2, 3, 1], which robs houses 0 and 2.
Ranges off by one: the two streets are 0..n−2 and 1..n−1, each with n − 1 houses.

Summary

The circle adds one rule: the first and last houses cannot both be robbed. Leave out each end in turn, solve the two straight streets with House Robber, and return the larger. O(n) time, O(1) extra space.

House Robber

Coin Change