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.
Open on LeetCode ↗Intuition
The circle adds exactly one new constraint: houses 0 and n-1 cannot both be robbed. Rather than inventing a circular DP, notice what that constraint implies — any optimal solution either leaves out the first house or leaves out the last one (possibly both). So run the linear House Robber solver twice, once on nums[0..n-2] and once on nums[1..n-1], and take the better result. Each window is a plain line with no wraparound, so the original algorithm applies untouched.
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
Isolate what actually changed
House Robber II is House Robber plus one adjacency: 0 and n-1 are neighbours. Every other constraint is identical. Rewriting the DP to handle wraparound means threading a 'did I take the first house?' flag through every state, doubling the state space for one edge — a lot of machinery for a small change.
Split the one hard constraint into two easy problems
The new rule forbids taking both endpoints, so any valid solution falls into one of two overlapping cases: it omits house 0, or it omits house n-1. The optimum is in at least one of them. Case A is the linear problem on nums[1..n-1]; case B is the linear problem on nums[0..n-2]. Both windows are ordinary lines. Solutions omitting both endpoints are counted in both cases, which is harmless — we take a maximum, not a sum.
Run the linear solver twice and take the max
Call the House Robber routine on each window and return the larger answer. Two O(n) passes with O(1) space each. The only case needing care is n == 1, where one of the windows is empty — handle it up front by returning nums[0]. This reduce-to-a-solved-problem move is worth naming explicitly in an interview.
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.