House Robber II: Circular DP

You already know the house robber rules: rob any house you want, but never two adjacent ones. Now imagine the street bends into a circle. The last house connects back to the first, so robbing both of them sets off the alarm. That single extra edge changes the problem entirely.

This is LeetCode 213: House Robber II. If you have not worked through House Robber yet, start there. This problem adds one constraint: the houses are arranged in a circle, so the first and last houses are adjacent.

Why this problem matters

Circular constraints show up all over competitive programming and interviews. Whenever the end of a sequence wraps around to the beginning, you lose the ability to treat endpoints independently. House Robber II is the cleanest introduction to that idea.

The technique you learn here, breaking a circular problem into two linear subproblems, transfers directly to problems like Paint House II, circular arrangement scheduling, and any situation where the first and last elements interact.

It also reinforces a core DP skill: problem reduction. Instead of inventing a brand-new algorithm, you reduce the circular version to two calls of an algorithm you already know. That "reduce and reuse" thinking is one of the most powerful tools in your problem-solving toolkit.

Thinking it through

The circular adjacency means you can never rob both house 0 and house n-1. That is the only new constraint compared to the linear version. Every other pair of adjacent houses follows the same "no two neighbors" rule you already handled in House Robber I.

Think about it from the perspective of house 0. Either you rob it or you do not:

• If you rob house 0, then house n-1 is off limits. You are free to apply the standard linear DP on houses 0 through n-2.
• If you skip house 0, then house n-1 might be available. You apply the standard linear DP on houses 1 through n-1.

One of those two scenarios must contain the optimal answer. You do not know which one in advance, so you run both and take the maximum.

The two-pass insight

This is the entire algorithm:

1. Run the linear House Robber on nums[0..n-2] (exclude the last house).
2. Run the linear House Robber on nums[1..n-1] (exclude the first house).
3. Return the larger of the two results.

Each run guarantees that the first and last house in the original circle are never both robbed. Together, the two runs cover every valid combination.

def rob(nums):
    if len(nums) == 1:
        return nums[0]

    def rob_linear(houses):
        if not houses:
            return 0
        if len(houses) == 1:
            return houses[0]
        dp = [0] * len(houses)
        dp[0] = houses[0]
        dp[1] = max(houses[0], houses[1])
        for i in range(2, len(houses)):
            dp[i] = max(dp[i - 1], dp[i - 2] + houses[i])
        return dp[-1]

    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

The O(1) space version

Just like in the linear House Robber, each DP value depends only on the previous two. Replace the array with two variables.

def rob(nums):
    if len(nums) == 1:
        return nums[0]

    def rob_linear(houses):
        prev2 = 0
        prev1 = 0
        for num in houses:
            current = max(prev1, prev2 + num)
            prev2 = prev1
            prev1 = current
        return prev1

    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

The rob_linear helper is identical to the O(1) space solution from House Robber I. You call it twice with different slices of the input, and the max at the end handles the circular constraint.

Complexity analysis

Both approaches run the linear algorithm twice on arrays of length n-1. Two passes of O(n-1) is still O(n). The O(1) space version drops the DP array entirely.

Edge cases to watch for

• Single house: return nums[0]. With one house, there is no circular adjacency to worry about.
• Two houses: return max(nums[0], nums[1]). They are adjacent in both directions, so you can only rob one.
• Three houses: you can only rob one (any two of three houses in a circle are adjacent to each other in some direction). The two-pass approach handles this correctly.
• All equal values: e.g., [5, 5, 5, 5]. The answer is 10 (rob two non-adjacent houses). Both runs produce the same result.
• Large value at both ends: e.g., [100, 1, 1, 100]. You cannot take both ends. Run 1 gives 100 (take house 0), Run 2 gives 100 (take house 3). Answer is 100, not 200.

The building blocks

This problem demonstrates problem reduction: you transform a harder problem (circular DP) into two instances of an easier problem (linear DP) that you already know how to solve. The linear DP itself uses constant-state recurrence, the same building block behind Climbing Stairs and Decode Ways.

The structure:

• Reduction: circular array to two linear subarrays
• State: dp[i] = maximum money from the subarray up to index i
• Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
• Space optimization: two variables instead of an array

This "split the circle" technique applies whenever a circular constraint prevents you from using a standard linear approach. You will see the same idea in circular paint problems, ring scheduling, and any DP where the first and last elements interact.

From understanding to recall

You now understand the two-pass trick: break the circle, run the linear algorithm twice, take the max. But recognizing that pattern under interview pressure is a different skill from reading about it here. The gap between understanding and recall is real.

Spaced repetition closes that gap. You revisit the circular reduction at increasing intervals, write it from scratch each time, and after a few reps the two-pass decomposition becomes automatic. No more second-guessing whether to exclude the first house or the last house in each run.

Related posts

• House Robber - The linear version, same DP recurrence without the circular constraint
• Climbing Stairs - The foundation of constant-state linear DP
• Decode Ways - Another linear DP with two-variable optimization