House Robber II

LeetCode 213: House Robber II Solution & Explanation

Problem Overview

TL;DR: The optimal solution breaks the circular constraint by decomposing the problem into two linear "House Robber" subproblems—one excluding the first house and one excluding the last—and returning the maximum result of the two.

House Robber II asks us to determine the maximum amount of money one can steal from a series of houses arranged in a circle. The critical constraint is that adjacent houses cannot be robbed on the same night. Because the arrangement is circular, the first house and the last house are considered neighbors. This implies you cannot rob both the first and the last house simultaneously.

This problem is a direct extension of the classic linear dynamic programming problem found in LeetCode 198. The LeetCode 213 solution requires handling the "wrap-around" adjacency effectively.

Brute Force Approach for House Robber II

The brute force approach attempts to explore every valid combination of houses. We can define a recursive function that makes a decision at every house: either rob it (and skip the next one) or skip it (and consider the next one).

To handle the circular constraint in a brute force manner, one might simply run the recursion while maintaining a flag indicating if the first house was robbed. If the recursion reaches the last house and the first house was also robbed, that path is invalid.

Pseudo-code:

function rob(index, robbedFirst):
    if index > last_index:
        return 0
    if index == last_index and robbedFirst:
        return 0 // Cannot rob last if first was robbed
    
    // Option 1: Rob current house
    val1 = nums[index] + rob(index + 2, index == 0 ? true : robbedFirst)
    
    // Option 2: Skip current house
    val2 = rob(index + 1, robbedFirst)
    
    return max(val1, val2)

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.

Algorithm Strategy: Dynamic Programming (DP) Patterns

1. Edge Case Handling: If the array nums has only 1 element, return nums[0]. The circular constraint does not apply to a single house.
2. Define Helper Function: Create a helper function robLinear(start, end) that solves the linear House Robber problem for a specific subarray range.
   • This function uses two variables, rob1 and rob2, to store the maximum loot at indices $i-2$ and $i-1$ respectively (Space Optimization).
   • Iterate from start to end.
   • Update newRob = max(rob1 + currentVal, rob2).
   • Update pointers: rob1 = rob2, rob2 = newRob.
   • Return rob2.
3. Execute Scenarios:
   • Calculate max1 = robLinear(0, N-2) (Includes first, excludes last).
   • Calculate max2 = robLinear(1, N-1) (Excludes first, includes last).
4. Final Result: Return max(max1, max2).

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])$.

Pattern Reuse Notes

The DP - 1D Array (Fibonacci Style) pattern and its logic are directly applicable to several other popular interview questions:

• LeetCode 70: Climbing Stairs - The base Fibonacci logic where $DP[i] = DP[i-1] + DP[i-2]$.
• LeetCode 91: Decode Ways - Similar state dependency where the decision at $i$ relies on the validity of single and double-digit formations ending at $i$.
• LeetCode 198: House Robber - The linear version of this problem; it is essentially the helper function used here.
• LeetCode 337: House Robber III - Applies the "rob or skip" logic to a Binary Tree structure, using a similar inclusion/exclusion principle (DFS instead of iterative array scan).

Reference Implementation

C++ Solution for LeetCode 213

1class Solution {
2public:
3    int rob(vector<int>& nums) {
4        int n = nums.size();
5        if (n == 0) return 0;
6        if (n == 1) return nums[0];
7        
8        // Solve two linear subproblems
9        // 1. Include first house, exclude last (0 to n-2)
10        // 2. Exclude first house, include last (1 to n-1)
11        return max(robLinear(nums, 0, n - 2), robLinear(nums, 1, n - 1));
12    }
13
14private:
15    // Helper function for linear House Robber logic
16    int robLinear(const vector<int>& nums, int start, int end) {
17        int prev2 = 0; // dp[i-2]
18        int prev1 = 0; // dp[i-1]
19        
20        for (int i = start; i <= end; ++i) {
21            int current = max(prev1, prev2 + nums[i]);
22            prev2 = prev1;
23            prev1 = current;
24        }
25        
26        return prev1;
27    }
28};

Java Solution for LeetCode 213

1class Solution {
2    public int rob(int[] nums) {
3        if (nums == null || nums.length == 0) return 0;
4        if (nums.length == 1) return nums[0];
5
6        // Calculate max loot for the two scenarios
7        int max1 = robLinear(nums, 0, nums.length - 2);
8        int max2 = robLinear(nums, 1, nums.length - 1);
9
10        return Math.max(max1, max2);
11    }
12
13    private int robLinear(int[] nums, int start, int end) {
14        int prev2 = 0; // Represents dp[i-2]
15        int prev1 = 0; // Represents dp[i-1]
16
17        for (int i = start; i <= end; i++) {
18            int current = Math.max(prev1, prev2 + nums[i]);
19            prev2 = prev1;
20            prev1 = current;
21        }
22
23        return prev1;
24    }
25}

Python Solution for LeetCode 213

1class Solution:
2    def rob(self, nums: List[int]) -> int:
3        n = len(nums)
4        if n == 0:
5            return 0
6        if n == 1:
7            return nums[0]
8            
9        # Define helper to solve linear version
10        def rob_linear(start, end):
11            rob1, rob2 = 0, 0
12            
13            # Iterate through the specified range
14            for i in range(start, end + 1):
15                # Standard DP transition: max(skip, rob + prev_rob)
16                new_rob = max(rob2, rob1 + nums[i])
17                rob1 = rob2
18                rob2 = new_rob
19            return rob2
20
21        # Compare scenario 0 to n-2 vs scenario 1 to n-1
22        return max(rob_linear(0, n - 2), rob_linear(1, n - 1))