House Robber (LC 198)

Pattern: Dynamic Programming (linear choice with constraint)
Difficulty: Medium
Key Concept: At each house, your best loot is either skip this house (take previous best) or rob this house plus best from two steps back—never two adjacent.

Problem Statement

You are a robber planning to rob houses along a street. Each house has a non-negative amount of money. Adjacent houses have connected security systems: you cannot rob two adjacent houses.

Given an integer array nums representing money in each house, return the maximum you can rob without alerting police (i.e. no two chosen indices are consecutive).

Input: nums (length ≥ 0 in extended thinking; problem often non-empty).
Output: int maximum sum.

Examples:

• [1,2,3,1] → 4 (rob 1 + 3).
• [2,7,9,3,1] → 12 (2 + 9 + 1).

---

1. Algorithm & Pseudocode

Brute force

1. For each subset of houses with no two adjacent, sum values; track max.
2. Enumerate via recursion: at index i, either skip (go to i+1) or take nums[i] and go to i+2.
3. Without memo: exponential branches.

Pseudocode:

function robFrom(i):
    if i >= n: return 0
    skip = robFrom(i + 1)
    take = nums[i] + robFrom(i + 2)
    return max(skip, take)

Optimal

1. Let take = best if we “end” having taken current; skip = best if we skip current.
2. Or: dp[i] = max(dp[i-1], nums[i] + dp[i-2]) with dp[-1]=0, dp[0]=nums[0].
3. O(1) space: keep prev2, prev1, roll forward.

Pseudocode (constant space):

prev2 = 0
prev1 = 0
for x in nums:
    cur = max(prev1, x + prev2)
    prev2 = prev1
    prev1 = cur
return prev1

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why not greedy by value: A very large house might force you to skip two neighbors that together beat it (e.g. [2,10,1,1,10]).

Why max(skip, take) is complete: At house i the only decisions are “don’t rob here” (inherit best up to i-1) or “rob here” (add nums[i] to best up to i-2). You cannot rob i and i-1.

Why O(1) works: dp[i] only needs i-1 and i-2, not full history.

---

3. The Dry Run

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

step	x	prev2	prev1	cur = max(prev1, x+prev2)
init	—	0	0	—
1	2	0	2	max(0,2+0)=2
2	7	2	7	max(2,7+0)=7
3	9	7	11	max(7,9+2)=11
4	3	7	11	max(11,3+7)=11
5	1	11	12	max(11,1+11)=12

---

4. Java Solution

Brute Force

public class Solution {
    public int rob(int[] nums) {
        return dfs(nums, 0);
    }

    private int dfs(int[] nums, int i) {
        if (i >= nums.length) {
            return 0;
        }
        int skip = dfs(nums, i + 1);
        int take = nums[i] + dfs(nums, i + 2);
        return Math.max(skip, take);
    }
}

Time: O(2^n) worst. Space: O(n) stack.

Optimal

public class Solution {
    public int rob(int[] nums) {
        int prev2 = 0;
        int prev1 = 0;
        for (int x : nums) {
            int cur = Math.max(prev1, x + prev2);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Time: O(n). Space: O(1).

---

5. The “Java vs. Others” Edge

• int suffices for typical constraints; for huge sums use long if interviewer asks.
• Iterative DP is clearer in Java interviews than stream reductions; avoid boxing.
• Memoized top-down uses int[] memo indexed by i—same complexity, more stack.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute DFS	O(2^n)	O(n)	Overlapping subproblems
DP array	O(n)	O(n)	dp[i] form
Two variables	O(n)	O(1)	Rolling max