House Robber

Difficulty: Medium
Topics: Array, Dynamic Programming
Link: https://leetcode.com/problems/house-robber/

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:


Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:


Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400

Solution

1. Problem Deconstruction

Technical Restatement:
Given an array nums of non-negative integers, select a subset of non-consecutive elements that maximizes their sum. Formally, find the maximum value of $\sum_{i \in S} \text{nums}[i]$ where $S$ contains no two consecutive integers.

Beginner Explanation:
Imagine you’re a thief who wants to rob houses on a street. Each house has money, but you can’t rob two houses next to each other or alarms go off. Your job is to figure out the best houses to rob to get the most money without getting caught.

Mathematical Formulation:
Let $f(i)$ denote the maximum money obtainable up to house $i$ . The recurrence is:

f(i) = \max\left(f(i-1),\ f(i-2) + \text{nums}[i]\right)

Base cases: $f(0) = \text{nums}[0]$ , $f(1) = \max(\text{nums}[0], \text{nums}[1])$ .

Constraint Analysis:

$1 \leq \text{nums.length} \leq 100$ :
- Allows O(n) and O(n²) approaches. Brute-force (O(2ⁿ)) is impractical even for n=30.
- Edge Case: Single-element arrays must return nums[0].
$0 \leq \text{nums}[i] \leq 400$ :
- No risk of integer overflow in standard programming languages.
- Edge Case: All zeros → return 0.

2. Intuition Scaffolding

Analogies:

Real-World: Choosing rest stops on a road trip where you can’t stop at two consecutive exits to maximize scenery points.
Gaming: Selecting non-adjacent tiles in a grid-based game to place towers for maximum damage.
Math: Maximizing the sum of node values in a path graph without selecting adjacent nodes (weighted independent set).

Common Pitfalls:

Greedy Selection of Local Maxima: Picking the largest value first may exclude higher cumulative sums.
- Counterexample: [3, 2, 3, 100] → Greedy picks 3, skips 100 → total 6 vs optimal 102.
Ignoring Overlapping Subproblems: Recomputing the same sub-decisions in brute force.
Misinitializing DP Base Cases: Forgetting to handle n=1 or n=2 correctly.
Overlooking Zero Values: Assuming all houses have positive money.
Space Inefficiency: Using O(n) space instead of O(1) for DP.

3. Approach Encyclopedia

Brute Force (Recursive):

Pseudocode:

def rob(nums):
    def helper(i):
        if i < 0: return 0
        return max(helper(i-1), helper(i-2) + nums[i])
    return helper(len(nums)-1)

Complexity:
Time: O(2ⁿ) due to repeated subproblems. Space: O(n) recursion stack.

Dynamic Programming (Optimal):

Pseudocode:

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

Complexity Proof:
- Time: O(n) → Single pass through the array.
- Space: O(1) → Only two variables track state.
Visualization:
```
Index: 0 1 2 3  
Nums:  1 2 3 1  
DP:    1 2 4 4  
```
Each step chooses between previous max (prev1) or current + prev2.

4. Code Deep Dive

Line-by-Line Breakdown:

def rob(nums):
    prev1 = prev2 = 0  # Tracks max at i-1 and i-2 positions.
    for num in nums:
        current = max(prev1, prev2 + num)  # Decision: rob current or not.
        prev2, prev1 = prev1, current  # Shift window forward.
    return prev1  # Final max after processing all houses.

Edge Case Handling:

Example 1 ([1,2,3,1]):
- prev1 evolves: 0 → 1 → 2 → 4 → 4. Final result 4.
Example 2 ([2,7,9,3,1]):
- prev1 updates: 0 → 2 →7 →11 →11 →12. Returns 12.

5. Complexity War Room

Hardware Considerations:

At n=100, the loop runs 100 times → negligible memory (~200 bytes for variables). Fits in CPU cache.

Approach Comparison:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(2ⁿ)	O(n)	6/10	❌
DP (Optimal)	O(n)	O(1)	9/10	✅

6. Pro Mode Extras

Variants:

Circular Houses (LeetCode 213): Compute max of rob(nums[1:]) and rob(nums[:-1]).
Rob k Houses: Extend DP state to track remaining houses or transactions.

Interview Cheat Sheet:

First Mention: Always state time/space complexity upfront.
Key Insight: “This is a classic DP problem where we track the optimal decision at each step without re-computation.”
Test Cases: Always test n=1, n=2, and alternating large/small values.

#198 - House Robber