House Robber II — Breaking Down the Circular Problem (Step-by-Step)

House Robber II adds one word to the original problem — circular. That single change seems to make everything harder. But here’s the trick: it actually reduces to two House Robber I problems. Solve each one, take the max, and you’re done.

Problem Statement

Examples

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Understanding the Test Cases

The first test case [1, 2, 3, 1] — you can rob house 0 (1) and house 2 (3) for a total of 4. House 0 and house 3 are adjacent in the circle, but we didn’t choose both, so no alarm.

The second test case [9, 1, 2, 9] shows the real constraint. In the original House Robber I, you could grab both 9s since they aren’t adjacent in a row. But here, the houses wrap around — house 0 and house 3 are neighbours. So you have to choose: rob house 0 (9) and house 2 (2) for 11, or rob house 1 (1) and house 3 (9) for 10. The answer is 11.

“Brute force and greedy both fail here — just like in House Robber I. The trick is to recognise which part of this problem is new and which part is already solved.”

The Key Insight — The Circular Problem Hides Two Linear Problems

The Two Scenarios — Visualised

For nums = [1, 2, 3, 1] (n=4), the two subarrays we pass to House Robber I are:

The Algorithm — Step by Step

Dry Run of the Code — nums = [2, 7, 9, 3, 1]

n = 5. Skip-last subarray: [2, 7, 9, 3]. Skip-first subarray: [7, 9, 3, 1]. Rolling variables start at prev2=0, prev1=0.

Scenario 1 — skip_last = [2, 7, 9, 3]

Scenario 2 — skip_first = [7, 9, 3, 1]

The Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        # Base case: only one house, no circular adjacency to handle
        if len(nums) == 1:
            return nums[0]

        def robLinear(houses: List[int]) -> int:
            """House Robber I on a non-circular array — O(n) time, O(1) space."""
            prev2, prev1 = 0, 0
            for val in houses:
                curr  = max(prev1, prev2 + val)
                prev2 = prev1
                prev1 = curr
            return prev1

        # Scenario 1: skip last house → houses 0 to n-2
        # Scenario 2: skip first house → houses 1 to n-1
        return max(robLinear(nums[:-1]), robLinear(nums[1:]))

The robLinear helper is identical to the House Robber I solution — not re-engineered, just reused. That’s the key pattern to highlight in an interview: recognise that you’re building on a solved subproblem, not starting from scratch.

Edge Cases

Time and Space Complexity

“Time is O(n) — the same as House Robber I, just run twice. Space is O(n) because of the list slices. To get true O(1) extra space, pass start and end indices to the helper and iterate over the original array directly.”

Interview Checklist for House Robber II

• Mention House Robber I first — this solution is built on top of it
• State the only new constraint: first and last houses are adjacent in a circle
• Explain that you can’t rob both house 0 and house n−1 → two exhaustive cases
• Case 1: skip last house → robLinear on nums[0..n−2]
• Case 2: skip first house → robLinear on nums[1..n−1]
• Answer = max of both cases
• Handle n=1 as a base case before running the two-subarray logic
• Describe robLinear: two rolling variables, curr = max(prev1, prev2 + val)
• State O(n) time and O(n)/O(1) space depending on implementation
• Trace through the dry run with [9,1,2,9] to show the circular constraint being enforced

Related Problems to Practice

If you can explain House Robber II cleanly, try these next: