House Robber II
Same as House Robber, but the houses are arranged in a circle — the first and last are now adjacent. Return the maximum loot.
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 1000
Intuition
House robber ii arranges the houses in a circle, so the first and last are now adjacent and cannot both be robbed. Everything else is unchanged from the original.
That single change breaks the linear DP, because the recurrence has no way to remember a decision made at the very start when it reaches the end.
The resolution avoids new machinery entirely. Note that the first and last houses can never both be robbed, which means every valid solution falls into one of two cases:
- Either the first house is excluded, or the last house is excluded — so run the linear solution twice, on nums[0..n-2] and nums[1..n-1], and take the larger result.
Each range is a straight line with no wraparound, so the original recurrence applies unmodified. Excluding one end in each run guarantees the two are never both taken.
The cases deliberately overlap — solutions robbing neither end appear in both ranges. That is harmless, since taking the maximum cannot double-count; it only needs each valid solution to appear at least once.
The edge case that breaks naive implementations is a single house. Both ranges are then empty and return 0, losing the only available value, so n == 1 must return nums[0] directly.
Two houses work without special handling: the ranges are [nums[0]] and [nums[1]], and the maximum is the larger, which is correct.
The cost is two linear passes, so it remains O(n) time and O(1) space.
The circle means the first and last houses are adjacent, so they can't both be taken. That single constraint splits into two independent linear problems — exclude the last house, or exclude the first — and the answer is the better of the two runs.
Approach
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n) time and O(1) space.
Identify what the circle breaks
The first and last houses are now adjacent, and the linear recurrence cannot remember a first-house decision by the time it reaches the last.
Split into two cases
The two ends can never both be robbed, so every solution either excludes the first house or excludes the last. These two cases cover all possibilities.
Run the linear solution twice
Apply the original House Robber recurrence to nums[0..n-2] and to nums[1..n-1]. Each range is a straight line, so nothing about the recurrence changes.
Take the larger result
The answer is the maximum of the two runs. Solutions robbing neither end appear in both ranges, but overlap is harmless when taking a maximum.
Handle the single house
With n == 1, both ranges are empty and return 0, losing the only value. Return nums[0] directly before splitting.
Let two houses fall out
The ranges become [nums[0]] and [nums[1]], and the maximum is the larger — correct with no special handling needed.
Cost of the approach
Two linear passes give O(n) time and O(1) space, the same complexity as the original problem.
Solution & live demo
Common pitfalls
Trying to handle the wraparound in one pass
# extra state tracking whether house 0 was taken
return max(line(nums[:-1]), line(nums[1:]))
Threading that flag through the recurrence doubles the state and is easy to get subtly wrong. Splitting into two runs of the linear solution reuses proven code and makes the constraint obvious.
Not special-casing a single house
return max(line(nums[:-1]), line(nums[1:]))
if len(nums) == 1:
return nums[0]With one house both slices are empty, so both runs return 0 and the answer is wrong. The circle degenerates when there's nothing for the first and last to conflict over.
Dropping only one end
return line(nums[:-1])
return max(line(nums[:-1]), line(nums[1:]))
Excluding the last house forbids a solution whose optimum includes it — on [1, 2, 3, 1] rotated so the best plan ends at the final house, that run misses the answer. Both exclusions must be tried.
Edge cases
Both windows would be empty, so return nums[0] before splitting. The circular constraint has nothing to act on with one house.
The windows are [nums[0]] and [nums[1]], giving max(nums[0], nums[1]) — correct, since they are adjacent both ways round.
Only one house can ever be robbed, and taking the maximum over the two windows finds the largest.
It appears in both windows and is returned by whichever is larger; no double-counting occurs because we take a max.