Time Complexity: $O(2^N)$. At every step, the recursion branches into two possibilities. This exponential growth makes the solution infeasible for $N$ up to 100. Why it fails: The approach performs redundant calculations for overlapping subproblems (e.g., the optimal way to rob houses 5 through 10 is calculated multiple times). This leads to a Time Limit Exceeded (TLE) error.

Core Insight for House Robber II

The primary challenge in House Robber II is the circular dependency: House $0$ and House $N-1$ are neighbors. This breaks the simple linear recurrence relation used in House Robber I.

However, we can simplify the circle into linear segments based on a key observation: You cannot rob both House $0$ and House $N-1$.

This constraint leaves us with exactly two scenarios covering all valid possibilities:

1. Scenario A: We include House $0$ in our consideration. Consequently, we must exclude House $N-1$. The problem becomes finding the max loot in the linear range nums[0...N-2].
2. Scenario B: We exclude House $0$ from our consideration. Consequently, House $N-1$ can be included. The problem becomes finding the max loot in the linear range nums[1...N-1].

By solving these two linear subproblems, we effectively break the circle. The answer to the original circular problem is simply max(Scenario A, Scenario B).

Each scenario is now a standard linear "House Robber" problem, which is solved using the Fibonacci-style recurrence: $DP[i] = \max(DP[i-1], \text{nums}[i] + DP[i-2])$

Visual Description: Imagine the state transition as a sliding window of two variables, prev1 and prev2. As we iterate through the array, prev1 represents the maximum loot up to the previous house, and prev2 represents the maximum loot up to the house before that. At current house $i$, we calculate the new maximum and shift the window forward. We perform this linear scan twice: once for the array excluding the tail, and once for the array excluding the head.

Execution Flow

Consider input nums = [2, 3, 2]. Length is 3.

1. Check Edge Case: Length is not 1. Proceed.
2. Split Problem:
   • Range 1: Indices 0 to 1 (Values [2, 3]).
   • Range 2: Indices 1 to 2 (Values [3, 2]).
3. Process Range 1 ([2, 3]):
   • Initialize rob1 = 0, rob2 = 0.
   • House 0 (Value 2): new = max(0 + 2, 0) = 2. rob1=0, rob2=2.
   • House 1 (Value 3): new = max(0 + 3, 2) = 3. rob1=2, rob2=3.
   • Result: 3.
4. Process Range 2 ([3, 2]):
   • Initialize rob1 = 0, rob2 = 0.
   • House 1 (Value 3): new = max(0 + 3, 0) = 3. rob1=0, rob2=3.
   • House 2 (Value 2): new = max(0 + 2, 3) = 3. rob1=3, rob2=3.
   • Result: 3.
5. Final Comparison: max(3, 3) = 3.

Proof of Correctness

The correctness relies on the fact that the circular constraint only adds one restriction: indices $0$ and $N-1$ cannot be chosen together. The set of all valid robbing plans can be partitioned into two subsets:

1. Plans that definitively do not include index $N-1$. This is covered by solving for range 0 to N-2.
2. Plans that definitively do not include index $0$. This is covered by solving for range 1 to N-1.

Any valid plan must belong to at least one of these subsets. By taking the maximum of the optimal solutions for both subsets, we guarantee finding the global maximum for the circular arrangement. The internal logic of the linear solver is proven correct via induction on the recurrence relation $DP[i] = \max(DP[i-1], nums[i] + DP[i-2])$.

Reference Implementation

C++ Solution for LeetCode 213

cpp
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        // Solve two linear subproblems
        // 1. Include first house, exclude last (0 to n-2)
        // 2. Exclude first house, include last (1 to n-1)
        return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
    }

private:
    // Helper function for linear House Robber logic
    int robLinear(const vector<int>& nums, int start, int end) {
        int prev2 = 0; // dp[i-2]
        int prev1 = 0; // dp[i-1]
        
        for (int i = start; i <= end; ++i) {
            int current = max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }
        
        return prev1;
    }
};

Java Solution for LeetCode 213

java
class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        // Calculate max loot for the two scenarios
        int max1 = robLinear(nums, 0, nums.length - 2);
        int max2 = robLinear(nums, 1, nums.length - 1);

        return Math.max(max1, max2);
    }

    private int robLinear(int[] nums, int start, int end) {
        int prev2 = 0; // Represents dp[i-2]
        int prev1 = 0; // Represents dp[i-1]

        for (int i = start; i <= end; i++) {
            int current = Math.max(prev1, prev2 + nums[i]);
            prev2 = prev1;
            prev1 = current;
        }

        return prev1;
    }
}

Python Solution for LeetCode 213

python
class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
            
        # Define helper to solve linear version
        def rob_linear(start, end):
            rob1, rob2 = 0, 0
            
            # Iterate through the specified range
            for i in range(start, end + 1):
                # Standard DP transition: max(skip, rob + prev_rob)
                new_rob = max(rob2, rob1 + nums[i])
                rob1 = rob2
                rob2 = new_rob
            return rob2

        # Compare scenario 0 to n-2 vs scenario 1 to n-1
        return max(rob_linear(0, n - 2), rob_linear(1, n - 1))