House Robber II (circular) Explained: Tracing [2, 3, 2]

Imagine you are planning a heist in a suburban neighborhood where houses are arranged in a closed loop, represented by the circular array [2, 3, 2]. Your standard rule remains the same: robbing two adjacent houses alerts the police. In a normal street, you can safely look at houses from start to finish. But when the street curls into a circle, house 0 at the start and house 2 at the end suddenly become neighbors, meaning you can no longer choose both of them even if they are physically separated in a flat array list.

To see why standard linear logic fails, contrast this with our linear warmup array [2, 1, 1, 2]. On a straight road, you can grab the first house (2) and the last house (2) for a maximum stash of 4, because they sit at opposite ends of a finite line. But apply that same greedy or independent logic to the circular [2, 3, 2], and a naive solver might blindly combine house 0 (2) and house 2 (2), resulting in an illegal haul of 4 that violates the circular security ring.

We need a way to strip away the circular constraint without losing the neighborhood's topology. Without a systematic strategy, you either under-rob by ignoring valid wrap-around combinations or get caught by the invisible seam connecting the first and last houses.

In our working example of nums = [2, 3, 2], house 0 (2) sits right next to house 2 (2). This circular boundary prevents us from running a single linear dynamic programming pass, because taking both the first and last house violates the adjacency rule. How do we eliminate a circular dependency without rewriting our entire state machine? We force a choice on the very first house.

If we decide to include the first house, we are strictly forbidden from robbing the last house. That shrinks our search space down to a linear street from index 0 to $n-2$. Conversely, if we exclude the first house, our street is free to consider the last house, shifting our valid range from index 1 to $n-1$.

Let us map this back to our linear warmup of [2, 1, 1, 2] to see how standard linear DP evaluates a non-circular path. In a linear arrangement, the recurrence relation relies only on local choices: at each house, we either skip it and keep the previous maximum, or rob it and add its loot to the maximum from two houses ago. For a circular array, we simply run this identical linear engine twice: once over nums[:-1] and once over nums[1:].

* Pass A (House 0 eligible): Evaluate linear House Robber on slice nums[0] through nums[n-2]. For [2, 3, 2], this slice is [2, 3].
* Pass B (House $n-1$ eligible): Evaluate linear House Robber on slice nums[1] through nums[n-1]. For [2, 3, 2], this slice is [3, 2].

Try this: Given a circular street represented by nums = [2, 3, 2], write out the two explicit linear slices that our algorithm must check before taking their maximum.

Let us trace our locked example step by step to see how the two-pass linear strategy solves the circular constraint. We will examine both the linear warmup [2, 1, 1, 2] and the circular neighborhood [2, 3, 2].

Given

- Linear Warmup: nums = [2, 1, 1, 2]
- Circular Neighborhood: nums = [2, 3, 2]

Steps for Linear Warmup ([2, 1, 1, 2])

Because this street is linear, we run standard House Robber across the full array indices 0 to 3:
- At index 0: prev2 = 0, current = max(0 + 2, 0) = 2. State: prev2 = 0, prev1 = 2.
- At index 1 (value = 1): current = max(2, 0 + 1) = 2. State: prev2 = 2, prev1 = 2.
- At index 2 (value = 1): current = max(2, 2 + 1) = 3. State: prev2 = 2, prev1 = 3.
- At index 3 (value = 2): current = max(3, 2 + 2) = 4. State: prev2 = 3, prev1 = 4.
- Linear Result: 4 (robbing index 0 and index 3).

Steps for Circular Neighborhood ([2, 3, 2])

Because house 0 and house 2 are adjacent, we split into two linear subproblems:
1. Subproblem A (Excluding the last house): Range indices 0 to 1, meaning nums = [2, 3].
- At index 0 (2): prev2 = 0, prev1 = 2.
- At index 1 (3): max(2, 0 + 3) = 3.

2. Subproblem B (Excluding the first house): Range indices 1 to 2, meaning nums = [3, 2].
- At index 1 (3): prev2 = 0, prev1 = 3.
- At index 2 (2): max(3, 0 + 2) = 3.

Result

Take the maximum of our two subproblems: $\max (3,3)=3$. Notice how we avoided robbing both the first house (2) and the last house (2) simultaneously.

Try this: def rob_linear(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, prev2 + n)
return prev1

Now that we have traced the linear warmup [2, 1, 1, 2] and the circular house layout [2, 3, 2], it is time to test your mental model on a slightly different neighborhood. Imagine the city council changes the street layout to a new circular block with the loot values [1, 2, 3, 1]. Remember our core principle: because house 0 and house $n-1$ are connected in a circle, you can never rob both of them in the same night.

To find the maximum loot, you must split this circular arrangement into two distinct linear subproblems, solve each using the linear house robber recurrence, and then combine their results. Before looking ahead, trace out the exact two linear slices you need to evaluate for [1, 2, 3, 1], write down the maximum for each slice, and determine the final answer.

def rob_circular(nums):
    # TODO: Handle edge cases like len(nums) == 1
    # TODO: Solve linear range nums[:-1]
    # TODO: Solve linear range nums[1:]
    # TODO: Return the maximum of both ranges
    pass

# Test case:
print(rob_circular([1, 2, 3, 1]))  # Expected output: 4

Now that you have mastered the dual-linear reduction strategy for circular streets like our working example $\text{nums}=[2,3,2]$, you can apply this exact structural insight to any ring-shaped resource allocation problem. Recall that the fundamental obstacle in the circular layout is the wrap-around edge connecting the first house $\text{nums}[0]$ and the last house $\text{nums}[n-1]$. By forcing a separation into two independent linear subranges—one omitting the last house and one omitting the first house—you completely bypass the circular constraint.

To solidify this transfer, imagine you are handed a larger circular street layout represented by the array $\text{nums}=[1,2,3,1]$. Just as we did for $[2,3,2]$, your job is to construct the two linear arrays, run the single-pass dynamic programming routine on each, and combine their outcomes using the $\max$ operator. This blueprint generalizes beyond houses; any dynamic programming problem featuring a cyclical dependency can be cracked by breaking a single critical link and solving the resulting linear endpoints.

Given an array $\text{nums}$ of length $n$:

1. Check the base case: if $n=1$, return $\text{nums}[0]$ immediately without running the helper function.
2. Define a linear helper function $\text{robLine}(a,b)$ that computes the maximum loot for the slice from index $a$ to index $b$.
3. Compute $\text{case1}=\text{robLine}(0,n-2)$ to cover the scenario where you exclude the final house.
4. Compute $\text{case2}=\text{robLine}(1,n-1)$ to cover the scenario where you exclude the first house.
5. Return $\max (\text{case1},\text{case2})$ as your final answer.

Try this: Given nums = [1, 2, 3, 1], apply the 5-step transfer recipe to find the maximum loot without robbing adjacent circular neighbors.