House Robber II (LeetCode 213)

The problem

Same rules as House Robber: nums[i] is the money in house i, and you cannot rob two adjacent houses. The twist is that the houses form a circle, so the first and last houses are neighbours too. Return the most you can take. There is at least one house.

Input:  nums = [2, 3, 2]
Output: 3

Houses 0 and 2 are adjacent on the circle, so you cannot take both 2s. The best is the single house worth 3.

How to think about it

Start with brute force. Try every subset of houses that has no two neighbours on the circle. That is O(2ⁿ), and the wrap-around makes even the recursive DP awkward to state directly.

The key insight: the circle only adds one constraint. The first and last houses can’t both be robbed. So in any valid plan, at least one of them is left alone. That splits the problem into two cases: ignore the first house (rob from nums[1:]) or ignore the last house (rob from nums[:-1]). Each case is a straight line, which is plain House Robber.

Take the better of two linear runs. Every valid circular plan fits inside at least one of those two lines, and every plan in either line is valid on the circle. So max(line(nums[1:]), line(nums[:-1])) is exactly the answer.

Which pattern is this? 1-D DP, reusing a solved problem. The tell is “a circular version of a linear DP”: break the cycle by fixing what happens at the seam, then solve each linear case.

Approach

1. If there is only one house, return its value (both slices would be empty otherwise).
2. Define line(arr) as the two-variable House Robber.
3. Return the larger of line(nums[1:]) and line(nums[:-1]).

Solution

def rob2(nums):
    if len(nums) == 1: return nums[0]             # one house: no circle conflict
    def line(arr):                                # plain House Robber on a row
        prev, cur = 0, 0
        for n in arr: prev, cur = cur, max(cur, prev + n)
        return cur
    return max(line(nums[1:]), line(nums[:-1]))   # drop first, or drop last
# rob2([2,3,2]) -> 3

Dry run

On [2, 3, 2], tracing both linear runs:

Both runs return 3, so the answer is 3. On [1, 2, 3, 1] the runs give 3 and 4, and the answer is 4.

Complexity

• Time: O(n). Two linear passes.
• Space: O(n) as written, O(1) with indices. The slices nums[1:] and nums[:-1] copy the list. Pass start and end indices to line if you need constant extra space.

Edge cases and pitfalls

• One house must be special-cased; without it both slices are empty and you return 0.
• Two houses ([1, 5]): the runs are [5] and [1], giving 5. Correct, since they are adjacent.
• Running House Robber once on the full array can pick both ends and overcount.
• Trying to “fix” the seam inside one pass with extra flags works but is easy to get wrong; the two-run split is cleaner to explain.

Related problems

• House Robber (LeetCode 198): the linear version this solution calls twice.
• House Robber III (LeetCode 337): the same rule on a tree instead of a line.
• Gas Station (LeetCode 134): another circular-array problem where breaking the circle is the key step.