House Robber

LeetCode 198: House Robber Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses dynamic programming to iteratively determine the maximum profit at each house by choosing between maintaining the previous maximum or adding the current house's value to the maximum from two houses back.

The House Robber problem asks us to determine the maximum amount of money one can steal from a row of houses. The input is an integer array nums where each element represents the cash in a specific house. The critical constraint is that you cannot rob two adjacent houses. If you rob house $i$, you cannot rob house $i-1$ or house $i+1$. We must return the maximum possible sum satisfying this non-adjacency constraint.

This is a classic optimization problem found in LeetCode 198, widely used in technical interviews to test understanding of state-based decision making.

Brute Force Approach for House Robber

The brute force approach attempts to explore every possible valid combination of houses to rob. This is typically implemented using recursion. For every house at index $i$, we make a binary decision:

1. Rob the current house $i$ and proceed to solve the subproblem for house $i-2$.
2. Skip the current house $i$ and proceed to solve the subproblem for house $i-1$.

The maximum of these two choices is the answer for the current step.

Pseudo-code:

function rob(index, nums):
    if index < 0:
        return 0
    
    // Choice 1: Rob current house + max from index-2
    robCurrent = nums[index] + rob(index - 2, nums)
    
    // Choice 2: Skip current house, take max from index-1
    skipCurrent = rob(index - 1, nums)
    
    return max(robCurrent, skipCurrent)

Time Complexity: $O(2^N)$
Each function call branches into two recursive calls. This creates a recursion tree with exponential growth.

Why it fails: The brute force solution fails due to overlapping subproblems. The function recalculates the optimal result for the same indices repeatedly. For an input size of $N=50$, $2^{50}$ operations is astronomically high, leading to a Time Limit Exceeded (TLE) error on LeetCode.

Algorithm Strategy: Dynamic Programming (DP) Patterns

We will implement the Fibonacci Style DP approach. Instead of maintaining a full array dp of size $N$, which would cost $O(N)$ space, we can optimize space to $O(1)$ by tracking only the two most recent states.

1. State Definition:

   • prev1: The maximum money robbable up to the previous house ($i-1$).
   • prev2: The maximum money robbable up to the house before the previous one ($i-2$).

2. Base Cases:

   • If the array is empty, return 0.
   • If the array has one element, return that element.

3. Iterative Transition:

   • Iterate through the array nums.
   • Calculate current_max using the recurrence: $\max(prev1, prev2 + nums[i])$.
   • Update pointers: prev2 becomes prev1, and prev1 becomes current_max.

4. Result:

   • After the loop, prev1 holds the maximum profit for the entire array.

Execution Flow

Consider nums = [2, 7, 9, 3, 1].

1. Initialization:

   • Set prev2 = 0 (imaginary house before index 0).
   • Set prev1 = 0 (imaginary house at index -1).

2. Iteration 1 (House 0, Value 2):

   • Calculate: $\max(prev1, prev2 + 2) \rightarrow \max(0, 0 + 2) = 2$.
   • Update: prev2 = 0, prev1 = 2.

3. Iteration 2 (House 1, Value 7):

   • Calculate: $\max(prev1, prev2 + 7) \rightarrow \max(2, 0 + 7) = 7$.
   • Update: prev2 = 2, prev1 = 7.

4. Iteration 3 (House 2, Value 9):

   • Calculate: $\max(prev1, prev2 + 9) \rightarrow \max(7, 2 + 9) = 11$.
   • Update: prev2 = 7, prev1 = 11.
   • Logic: Robbing house 2 (9) + house 0 (2) is better than skipping house 2 (keeping 7).

5. Iteration 4 (House 3, Value 3):

   • Calculate: $\max(prev1, prev2 + 3) \rightarrow \max(11, 7 + 3) = 11$.
   • Update: prev2 = 11, prev1 = 11.
   • Logic: Robbing house 3 (3) + house 1 (7) = 10. Skipping house 3 keeps 11. We skip.

6. Iteration 5 (House 4, Value 1):

   • Calculate: $\max(prev1, prev2 + 1) \rightarrow \max(11, 11 + 1) = 12$.
   • Update: prev2 = 11, prev1 = 12.

7. Final Output: Return prev1 (12).

Proof of Correctness

The algorithm's correctness relies on the principle of optimality. For the final solution to be optimal, its sub-solutions must also be optimal.

Let $P(i)$ be the maximum profit for the first $i$ houses. Base cases:

• $P(0) = 0$ (0 houses)
• $P(1) = nums[0]$

Inductive Step: Assume $P(k)$ correctly represents the max profit for $k$ houses for all $k < i$. For house $i$, there are only two mutually exclusive possibilities regarding the optimal set:

1. House $i$ is included. If so, house $i-1$ cannot be. The max profit is $nums[i] + P(i-2)$.
2. House $i$ is excluded. The max profit is simply $P(i-1)$.

Since we take the maximum of these two exhaustive cases ($\max(P(i-1), nums[i] + P(i-2))$), $P(i)$ must be optimal.

Pattern Reuse Notes

The DP - 1D Array (Fibonacci Style) pattern used in LeetCode 198 is highly transferable. Understanding this recurrence relation helps solve several other popular interview questions:

• LeetCode 70: Climbing Stairs: Identical recurrence $dp[i] = dp[i-1] + dp[i-2]$, but summing ways instead of maximizing value.
• LeetCode 91: Decode Ways: Similar "look back 1 or 2 steps" logic, but with conditional validity checks based on string characters.
• LeetCode 213: House Robber II: The same problem but with houses arranged in a circle. It is solved by running the House Robber I logic twice (once excluding the first house, once excluding the last).
• LeetCode 337: House Robber III: Applies the "rob or skip" logic to a Binary Tree structure, requiring a DFS approach rather than a linear loop.

Reference Implementation

C++ Solution for LeetCode 198

1class Solution {
2public:
3    int rob(vector<int>& nums) {
4        if (nums.empty()) return 0;
5        
6        // prev1 represents dp[i-1], prev2 represents dp[i-2]
7        int prev1 = 0;
8        int prev2 = 0;
9        
10        for (int num : nums) {
11            // Calculate max profit for current house
12            int temp = max(prev1, prev2 + num);
13            
14            // Shift states forward
15            prev2 = prev1;
16            prev1 = temp;
17        }
18        
19        return prev1;
20    }
21};

Java Solution for LeetCode 198

1class Solution {
2    public int rob(int[] nums) {
3        if (nums == null || nums.length == 0) {
4            return 0;
5        }
6        
7        // prev1 tracks the max money robbed up to the previous house
8        // prev2 tracks the max money robbed up to two houses ago
9        int prev1 = 0;
10        int prev2 = 0;
11        
12        for (int num : nums) {
13            // Recurrence: max(skip current, rob current + prev2)
14            int currentMax = Math.max(prev1, prev2 + num);
15            
16            // Update pointers for the next iteration
17            prev2 = prev1;
18            prev1 = currentMax;
19        }
20        
21        return prev1;
22    }
23}

Python Solution for LeetCode 198

1class Solution:
2    def rob(self, nums: List[int]) -> int:
3        # prev1 represents the max loot up to index i-1
4        # prev2 represents the max loot up to index i-2
5        prev1, prev2 = 0, 0
6        
7        for num in nums:
8            # Calculate the new max including or excluding current num
9            # Update prev1 and prev2 simultaneously
10            temp = max(prev1, prev2 + num)
11            prev2 = prev1
12            prev1 = temp
13            
14        return prev1