House Robber II takes the classic House Robber DP and bends the street into a circle. That one twist — the first and last houses become neighbors — is solved with a surprisingly clean trick: solve the linear problem twice.
Problem. Houses are arranged in a circle, so the first and last house are adjacent. You cannot
rob two adjacent houses. Given nums where nums[i] is the money in house i, return the maximum you
can rob without alerting the police.
Example: nums = [2, 3, 2] → answer 3 (you cannot rob houses 0 and 2 together, so the best is just
house 1 = 3).
The slow way first
You might try to extend the linear House Robber DP with extra bookkeeping: track whether you robbed the first house so you can forbid the last one. It works, but it tangles the recurrence with awkward edge cases and is easy to get wrong under interview pressure.
The question to ask: what actually makes this circular? Only one thing — house 0 and the last house are neighbors. So in any valid plan, at least one of them is left un-robbed.
The idea: solve the line twice
If the first or the last house must be skipped, then split into two plain (non-circular) problems:
- Pass A — ignore the last house: run linear House Robber on
nums[0..n-2]. - Pass B — ignore the first house: run linear House Robber on
nums[1..n-1].
Every legal circular plan lives inside one of those two slices, so the answer is the max of the two passes. Each pass is the ordinary "rob or skip" DP.
The linear helper keeps two running totals: cur (best including this house) and prev (best up to the previous house), updated with cur = max(cur, prev + money).
Walk through it
Step through the animation. Pass A scans houses [2, 3] (the last house greyed out) and lands on 3. Pass B scans [3, 2] (the first house greyed out) and also lands on 3. The final answer is max(3, 3) = 3 — rob only the middle house.
Pseudocode
if there is only one house:
return its money
best_A = linear_rob(nums without the last house)
best_B = linear_rob(nums without the first house)
return max(best_A, best_B)
linear_rob(houses):
prev, cur = 0, 0
for money in houses:
prev, cur = cur, max(cur, prev + money) # skip vs rob-this
return curThe Python solution
def rob(nums):
if len(nums) == 1:
return nums[0]
return max(rob_line(nums[:-1]), rob_line(nums[1:]))
def rob_line(houses):
prev, cur = 0, 0
for money in houses:
prev, cur = cur, max(cur, prev + money)
return cur- The single-house guard matters: with one house there is no slice to drop, so we just return it.
nums[:-1]is "everything but the last house" (Pass A);nums[1:]is "everything but the first" (Pass B).rob_lineis the plain House Robber: for each house,curbecomes the better of skipping it (keepcur) or robbing it (prev + money).- Line 9 is the heart of the DP — the rolling
prev, curupdate needs only O(1) memory. - We return
maxof the two passes because every valid circular plan omits at least one endpoint.
Complexity
| Case | Time | Notes |
|---|---|---|
| Two linear passes | O(n) (moderate) | each pass scans once |
| Total | O(n) (moderate) | two O(n) passes is still O(n) |
O(1) (fast)We pay only for two constant-memory sweeps. Reframing one hard circular problem as two easy linear ones costs nothing asymptotically.
When this pattern shows up
When a constraint is circular (first and last wrap around), a common move is to fix or remove one endpoint and solve the resulting linear problem — often once per choice of endpoint, then combine. The same idea appears in circular-array DP and ring-buffer problems.
Do not forget the single-house base case. nums[:-1] and nums[1:] are both empty when there is one
house, so both passes would return 0 and you would lose the only house. Handle len(nums) == 1 first.
Practice
For nums = [2, 3, 2], why can't we just run one linear House Robber over all three houses?
1. Why does solving two linear passes correctly handle the circular constraint?
2. What do nums[:-1] and nums[1:] represent?
3. What is the space complexity of this solution?
4. Why is the single-house base case needed?