House Robber II — Solution

Problem

You are a robber targeting a circular neighborhood: the houses are arranged in a ring, meaning the first house and the last house are neighbors. You cannot rob two adjacent houses without triggering the alarm. Given the amount of money in each house, find the maximum you can steal in one night.

• Input: nums = [2, 3, 2]
• Output: 3
• Explanation: Robbing house 1 (amount 3) is optimal — houses 0 and 2 are neighbors in the ring, so you can only pick one of them.

Counter-example showing why the circle matters:

• Input: nums = [1, 2, 3, 1]
• Output: 4
• Explanation: Rob house 0 (1) and house 2 (3) for 4 total; you cannot also take house 3 because it is adjacent to house 0 in the circle.

Intuition

The circular layout creates exactly one new constraint compared to the linear version: you cannot rob both the first house and the last house in the same night. That single constraint lets us split the problem cleanly — either house 0 is in your plan or it is not. If it is, house n-1 is off-limits; if it is not, house n-1 is fair game. Running the classic linear House Robber on each of the two resulting sub-ranges and taking the better result is both correct and optimal.

Solution — Two-Pass Linear DP

Reduce the circular problem to two straight-line problems. Pass 1 covers houses 0 through n-2 (excluding the last); pass 2 covers houses 1 through n-1 (excluding the first). Each pass uses O(1) rolling variables. Return the maximum of the two.

1. Return nums[0] immediately when there is only one house (the two-range split would create an empty range otherwise).
2. Define a helper rob_linear that scans an array segment keeping two rolling values: the best profit two steps back and the best profit one step back.
3. At each house, either skip it (keep the one-step-back value) or rob it (add its amount to the two-step-back value).
4. Run rob_linear on the range [0, n-2], then on [1, n-1].
5. Return the maximum of the two results.

1def rob(nums: list[int]) -> int:
2    if len(nums) == 1:
3        return nums[0]
4
5    def rob_linear(houses: list[int]) -> int:
6        prev_prev, prev = 0, 0
7        for amount in houses:
8            # skip this house (keep prev) or rob it (prev_prev + amount)
9            prev_prev, prev = prev, max(prev, prev_prev + amount)
10        return prev
11
12    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

Time: O(n) — two linear scans over the array, each visiting at most n-1 houses.
Space: O(1) — only two rolling variables are needed regardless of input size.

Complexity Summary

Common Mistakes

• Missing the single-house edge case: when n = 1 the two-range split produces an empty slice, causing the helper to return 0 instead of nums[0]. Guard this before splitting.
• Wrong second range endpoint: the two ranges are [0, n-2] and [1, n-1]. Using [1, n-2] on the second pass drops the last house entirely and under-counts.
• Initializing both rolling variables from nums[0]: starting prev_prev = nums[0] and prev = nums[0] double-counts the first element. Both should start at 0 and let the loop handle the first house normally.
• Attempting a single DP with an extra "used house 0" flag: this is correct but significantly more complex to implement correctly. The two-pass reduction is the idiomatic approach and should be reached for first.
• Passing the full array to rob_linear instead of the relevant slice: the whole point of the two-pass approach is to exclude one endpoint from each run — passing nums unsliced reintroduces the circular constraint.

Related Problems

• house-robber — the 1D version; rob_linear above is exactly this problem
• house-robber-iii — the same adjacent-constraint DP extended to a binary tree
• best-time-to-buy-and-sell-stock-with-cooldown — DP where a choice today forces a skip tomorrow, requiring careful state tracking
• partition-equal-subset-sum — DP on an array where a global constraint rules out many choices
• decode-ways — sequence DP where the recurrence looks one or two steps back, similar rolling-variable structure