213. House Robber
🔗 LeetCode Problem: 198. House Robber
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, Array, 1D DP
Problem Statement
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
🌳 Visual Understanding - Using [2, 7, 9, 3, 1]
The Problem We're Solving:
Street: [2, 7, 9, 3, 1]
🏠 🏠 🏠 🏠 🏠
H0 H1 H2 H3 H4
Goal: Rob maximum money WITHOUT robbing adjacent houses!
Rule: Can't rob two houses next to each other
✓ Rob H0 and H2 (not adjacent)
✗ Rob H0 and H1 (adjacent - alarm!)
Question: What's the maximum money we can steal? 🤔
Understanding the Constraint:
Street: [2, 7, 9, 3, 1]
VALID robbery plans:
━━━━━━━━━━━━━━━━━━━━
Rob houses: [0, 2, 4]
Money: 2 + 9 + 1 = 12 ✓ MAXIMUM!
Valid? 0↔2 not adjacent ✓, 2↔4 not adjacent ✓
Rob houses: [0, 2]
Money: 2 + 9 = 11 ✓
Valid? 0↔2 not adjacent ✓
Rob houses: [1, 3]
Money: 7 + 3 = 10 ✓
Valid? 1↔3 not adjacent ✓
Rob houses: [1, 4]
Money: 7 + 1 = 8 ✓
Valid? 1↔4 not adjacent ✓
INVALID robbery plans:
━━━━━━━━━━━━━━━━━━━━━
Rob houses: [0, 1]
Money: 2 + 7 = 9
Valid? 0↔1 ARE adjacent ✗ ALARM!
Rob houses: [1, 2, 3]
Money: 7 + 9 + 3 = 19
Valid? 1↔2 ARE adjacent ✗ ALARM!
Maximum valid money: 12 from [2, 9, 1] ✓
Decision Tree for [2, 7, 9, 3, 1]:
Start (position 0)
|
+-----------------+-----------------+
| |
ROB H0 ($2) SKIP H0
| |
v v
Can't rob H1! Position 1
Go to H2 |
| +--------------+--------------+
v | |
Position 2 ROB H1 ($7) SKIP H1
| | |
+----+----+ Can't rob H2! Position 2
| | Go to H3 |
ROB H2 SKIP H2 | (continues)
($9) | v
| v Position 3
v Position 3 |
Can't rob H3! (continues)
Go to H4
|
v
Position 4
|
+--+--+
| |
ROB SKIP
H4 H4
($1) ($0)
| |
v v
$2+$9+$1 $2+$9+$0
= $12 ✓ = $11
(Other branches give smaller values)
Best path: Rob H0($2) → Skip H1 → Rob H2($9) → Skip H3 → Rob H4($1)
Total: $12 ✓
Why This Is Interesting:
Sometimes the BIGGEST house isn't in the best plan!
Example: [2, 7, 9, 3, 1]
GREEDY (always take biggest available):
Take H2 ($9) first
Can't take H1 or H3
Can take H0 ($2) and H4 ($1)
Total: 9 + 2 + 1 = 12 ✓
But try: [2, 1, 1, 2]
GREEDY:
Take H0 ($2)
Skip H1
Take H2 ($1)
Skip H3
Total: 2 + 1 = 3
OPTIMAL:
Skip H0
Take H1 ($1)
Skip H2
Take H3 ($2)
Total: 1 + 2 = 3
Wait, same! Let me try: [1, 2, 3, 1]
GREEDY:
Take H2 ($3) - biggest
Can't take H1 or H3
Can take H0 ($1)
Total: 3 + 1 = 4 ✓
OPTIMAL:
Take H0 ($1)
Skip H1
Take H2 ($3)
Skip H3
Total: 1 + 3 = 4 ✓
Actually greedy works here! But consider: [5, 3, 4, 11, 2]
GREEDY:
Take H3 ($11) - biggest
Can't take H2 or H4
Can take H0 ($5) and... H1? No, H0 adjacent to H1
Total: 11 + 5 = 16 ✓
OPTIMAL:
Skip H0
Take H1 ($3)
Skip H2
Take H3 ($11)
Skip H4
Total: 3 + 11 = 14... wait that's worse!
Let's recalculate: [5, 3, 4, 11, 2]
Option 1: H0, H2, H4 = 5 + 4 + 2 = 11
Option 2: H0, H3 = 5 + 11 = 16 ✓
Option 3: H1, H3 = 3 + 11 = 14
Option 4: H1, H4 = 3 + 2 = 5
Greedy still wins! The point is: we need DP to be sure! 🎯
🧠 The AHA Moment - Why This Needs DP
The Key Decision at Each House:
Standing in front of house i, you have TWO choices:
CHOICE 1: ROB this house
→ Get money from house i
→ But CAN'T rob house i-1 (adjacent!)
→ Must use best plan from house i-2
CHOICE 2: SKIP this house
→ Get NO money from house i
→ But CAN rob house i-1 if you want
→ Can use best plan from house i-1
Choose whichever gives MORE money! 🎯
The Recursive Thinking:
Let rob(i) = "Maximum money robbing houses 0 to i"
rob(i) depends on:
- rob(i-1): best plan WITHOUT house i
- rob(i-2): best plan we can add house i to
Formula:
rob(i) = max(
rob(i-1), // Skip house i
rob(i-2) + nums[i] // Rob house i
)
This is RECURSIVE with OVERLAPPING SUBPROBLEMS!
Perfect for DP! 🎯
Visual Example: [2, 7, 9, 3, 1]
Building the solution step by step:
House 0 ($2):
rob(0) = 2
(Only one house, rob it!)
House 1 ($7):
Option 1: Skip H1, use rob(0) = 2
Option 2: Rob H1 = 7
rob(1) = max(2, 7) = 7
(Taking H1 is better!)
House 2 ($9):
Option 1: Skip H2, use rob(1) = 7
Option 2: Rob H2 + rob(0) = 9 + 2 = 11
rob(2) = max(7, 11) = 11
(Taking H2 with H0 is better!)
House 3 ($3):
Option 1: Skip H3, use rob(2) = 11
Option 2: Rob H3 + rob(1) = 3 + 7 = 10
rob(3) = max(11, 10) = 11
(Skipping H3 is better!)
House 4 ($1):
Option 1: Skip H4, use rob(3) = 11
Option 2: Rob H4 + rob(2) = 1 + 11 = 12
rob(4) = max(11, 12) = 12 ✓
(Taking H4 with previous plan is better!)
Answer: 12
Plan: Rob H0, H2, H4 → $2 + $9 + $1 = $12 ✓
🔴 Approach 1: Brute Force Recursion (Try All Combinations)
📐 Function Definition
Function Signature:
int rob(int[] nums)
int robFrom(int[] nums, int index)
What it represents:
Input Parameter nums:
- Array of money in each house
- Example: nums = [2, 7, 9, 3, 1]
Input Parameter index:
- Current house we're deciding about
- Example: index = 2 means "decide about house 2"
Return Value (int):
- Maximum money we can rob from house index onwards
- Example: robFrom(nums, 2) = max money from houses 2, 3, 4
Purpose: - At each house, try both options (rob or skip) - Recursively solve for remaining houses - Return the maximum
Key Understanding:
robFrom(nums, 0) means:
"What's the max money from ALL houses starting at 0?"
robFrom(nums, 2) means:
"What's the max money from houses 2, 3, 4?"
At each house:
Option 1: Rob it, skip next, solve from i+2
Option 2: Skip it, solve from i+1
Take whichever is larger!
💡 Intuition
The simplest idea: Try both options at each house!
Think of it like choosing candies in a row:
Houses: [2, 7, 9, 3, 1]
At house 0:
"Should I take $2?"
YES: Take $2, skip house 1, decide from house 2
→ $2 + robFrom(2)
NO: Don't take $2, decide from house 1
→ robFrom(1)
Choose whichever gives more money!
At house 2 (in the "YES" branch):
"Should I take $9?"
YES: Take $9, skip house 3, decide from house 4
→ $9 + robFrom(4)
NO: Don't take $9, decide from house 3
→ robFrom(3)
Continue recursively until we run out of houses!
Simple but SLOW (many repeated calculations)!
📝 Implementation
class Solution {
public int rob(int[] nums) {
return robFrom(nums, 0);
}
private int robFrom(int[] nums, int index) {
// Base case: no more houses
if (index >= nums.length) {
return 0;
}
// Option 1: Rob this house, skip next, continue from i+2
int robCurrent = nums[index] + robFrom(nums, index + 2);
// Option 2: Skip this house, continue from i+1
int skipCurrent = robFrom(nums, index + 1);
// Return the better option
return Math.max(robCurrent, skipCurrent);
}
}
🔍 Detailed Dry Run: nums = [2, 7, 9, 3, 1]
robFrom([2,7,9,3,1], 0)
├─ Option 1: Rob H0 ($2)
│ └─ $2 + robFrom([2,7,9,3,1], 2)
│ ├─ Option 1: Rob H2 ($9)
│ │ └─ $9 + robFrom([2,7,9,3,1], 4)
│ │ ├─ Option 1: Rob H4 ($1)
│ │ │ └─ $1 + robFrom([2,7,9,3,1], 6)
│ │ │ └─ index >= length → return 0
│ │ │ └─ Result: $1 + $0 = $1
│ │ │
│ │ ├─ Option 2: Skip H4
│ │ │ └─ robFrom([2,7,9,3,1], 5)
│ │ │ └─ index >= length → return 0
│ │ │ └─ Result: $0
│ │ │
│ │ └─ max($1, $0) = $1
│ │ └─ Result: $9 + $1 = $10
│ │
│ ├─ Option 2: Skip H2
│ │ └─ robFrom([2,7,9,3,1], 3)
│ │ ├─ Option 1: Rob H3 ($3)
│ │ │ └─ $3 + robFrom([2,7,9,3,1], 5)
│ │ │ └─ index >= length → return 0
│ │ │ └─ Result: $3 + $0 = $3
│ │ │
│ │ ├─ Option 2: Skip H3
│ │ │ └─ robFrom([2,7,9,3,1], 4)
│ │ │ └─ (calculated above) = $1
│ │ │
│ │ └─ max($3, $1) = $3
│ │ └─ Result: $3
│ │
│ └─ max($10, $3) = $10
│ └─ Result: $2 + $10 = $12 ✓
│
├─ Option 2: Skip H0
│ └─ robFrom([2,7,9,3,1], 1)
│ ├─ Option 1: Rob H1 ($7)
│ │ └─ $7 + robFrom([2,7,9,3,1], 3)
│ │ └─ (calculated above) = $3
│ │ └─ Result: $7 + $3 = $10
│ │
│ ├─ Option 2: Skip H1
│ │ └─ robFrom([2,7,9,3,1], 2)
│ │ └─ (calculated above) = $10
│ │
│ └─ max($10, $10) = $10
│ └─ Result: $10
│
└─ max($12, $10) = $12 ✓
Final Result: $12
Best plan: Rob H0 ($2), Rob H2 ($9), Rob H4 ($1)
The Problem - Repeated Calculations:
Notice robFrom(2) was calculated TWICE:
1. In the "Rob H0" branch
2. In the "Skip H0, Skip H1" branch
robFrom(3) was also calculated multiple times!
For larger arrays, this creates exponential work!
Example: For n=20 houses
Recursive tree has 2^20 = 1,048,576 nodes!
TOO SLOW! ⚠️
📊 Complexity Analysis
Time Complexity: O(2^n)
At each house, 2 choices (rob or skip)
Creates binary tree of recursive calls
Exponential growth!
For n=5: up to 32 calls
For n=10: up to 1024 calls
For n=20: over 1 million calls!
TOO SLOW! ❌
Space Complexity: O(n)
Recursion stack depth: O(n)
(In the worst case, we go through all houses)
Why This Fails:
❌ Exponential time - too slow
❌ Massive repeated calculations
❌ Can't handle n=100
✅ But shows the decision structure clearly!
🟡 Approach 2: Top-Down DP (Memoization - Remember Decisions)
📐 Function Definition
Function Signature:
int robFrom(int[] nums, int index, int[] memo)
What it represents:
Input Parameter memo:
- Memory array to cache results
- memo[i] = max money from house i onwards
- -1 = not calculated yet
- Other values = cached result
Purpose: - Same recursion as Approach 1 - BUT remember results to avoid recalculation - Each house calculated at most once!
Key Understanding:
First time at house 2:
- memo[2] = -1 (not calculated)
- Calculate: max money from houses 2,3,4
- Result: $10
- Store: memo[2] = $10
- Return: $10
Second time at house 2:
- memo[2] = $10 (already know!)
- Return immediately: $10
- No recalculation! ✨
This saves TONS of time!
💡 Intuition
Super simple: Remember what we've already figured out!
Think of it like remembering your route home:
WITHOUT MEMORY:
Every time you need to go from point A to B,
you recalculate the entire route.
Waste of time! ⚠️
WITH MEMORY:
First time: Calculate route, remember it
Next time: "Oh! I've been here before!"
→ Use remembered route
→ No recalculation! ✨
For house robbery:
First time at house 3:
→ Calculate: max money from houses 3,4
→ Remember: memo[3] = $3
Next time at house 3:
→ Look up: memo[3] = $3
→ Return immediately!
This is MEMOIZATION!
📝 Implementation
class Solution {
public int rob(int[] nums) {
int[] memo = new int[nums.length];
// Initialize with -1 to indicate "not calculated"
Arrays.fill(memo, -1);
return robFrom(nums, 0, memo);
}
private int robFrom(int[] nums, int index, int[] memo) {
// Base case
if (index >= nums.length) {
return 0;
}
// Check if already calculated
if (memo[index] != -1) {
return memo[index]; // Return cached result! ✨
}
// Option 1: Rob current house
int robCurrent = nums[index] + robFrom(nums, index + 2, memo);
// Option 2: Skip current house
int skipCurrent = robFrom(nums, index + 1, memo);
// Store result before returning
memo[index] = Math.max(robCurrent, skipCurrent);
return memo[index];
}
}
🔍 Detailed Dry Run: nums = [2, 7, 9, 3, 1]
Initial state:
memo = [-1, -1, -1, -1, -1]
↑ ↑ ↑ ↑ ↑
H0 H1 H2 H3 H4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
robFrom(nums, 0, memo)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Check memo[0] = -1 → NOT calculated yet
Option 1: Rob H0
→ $2 + robFrom(nums, 2, memo)
robFrom(nums, 2, memo):
Check memo[2] = -1 → NOT calculated yet
Option 1: Rob H2
→ $9 + robFrom(nums, 4, memo)
robFrom(nums, 4, memo):
Check memo[4] = -1 → NOT calculated yet
Option 1: Rob H4
→ $1 + robFrom(nums, 6, memo)
→ $1 + 0 = $1
Option 2: Skip H4
→ robFrom(nums, 5, memo)
→ 0
memo[4] = max($1, $0) = $1 ✓
Return $1
→ $9 + $1 = $10
Option 2: Skip H2
→ robFrom(nums, 3, memo)
robFrom(nums, 3, memo):
Check memo[3] = -1 → NOT calculated yet
Option 1: Rob H3
→ $3 + robFrom(nums, 5, memo)
→ $3 + 0 = $3
Option 2: Skip H3
→ robFrom(nums, 4, memo)
→ memo[4] = $1 ✓ (CACHE HIT!)
memo[3] = max($3, $1) = $3 ✓
Return $3
→ $3
memo[2] = max($10, $3) = $10 ✓
Return $10
→ $2 + $10 = $12
Option 2: Skip H0
→ robFrom(nums, 1, memo)
robFrom(nums, 1, memo):
Check memo[1] = -1 → NOT calculated yet
Option 1: Rob H1
→ $7 + robFrom(nums, 3, memo)
→ $7 + memo[3] ✓ (CACHE HIT!)
→ $7 + $3 = $10
Option 2: Skip H1
→ robFrom(nums, 2, memo)
→ memo[2] = $10 ✓ (CACHE HIT!)
memo[1] = max($10, $10) = $10 ✓
Return $10
→ $10
memo[0] = max($12, $10) = $12 ✓
Final memo state:
memo = [12, 10, 10, 3, 1]
↑ ↑ ↑ ↑ ↑
H0 H1 H2 H3 H4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: $12 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Cache hits saved us from recalculating:
- memo[4] used twice (once calculated, once cached)
- memo[3] used twice (once calculated, once cached)
- memo[2] used twice (once calculated, once cached)
Much faster! 🚀
📊 Complexity Analysis
Time Complexity: O(n)
Each house calculated at most once: O(n)
Each calculation: O(1)
Total: O(n) ✓
MUCH better than O(2^n)! 🚀
Space Complexity: O(n)
Memo array: O(n)
Recursion stack: O(n)
Total: O(n)
🟢 Approach 3: Bottom-Up DP (Build Solution from Start)
📐 Function Definition
DP Array Definition:
int[] dp = new int[n];
What dp[i] represents:
Index i:
- House number
- dp[i] represents houses 0 to i
Value dp[i] (int):
- dp[i] = Maximum money robbing houses 0 through i
- Example: dp[2] = max money from houses 0, 1, 2
Purpose: - Build solution table from START to END - No recursion needed! - Fill table once, use directly
Key Understanding:
For [2, 7, 9, 3, 1]:
dp[0] = 2 (max money from just H0)
dp[1] = 7 (max money from H0,H1)
dp[2] = 11 (max money from H0,H1,H2)
dp[3] = 11 (max money from H0,H1,H2,H3)
dp[4] = 12 (max money from all houses)
dp[4] = final answer! ✓
💡 Intuition
Think of it as building your fortune house by house:
You walk down the street, deciding at each house:
At H0 ($2):
Only one house → must rob it
dp[0] = $2
At H1 ($7):
Can rob H1 alone ($7) OR keep H0 ($2)
Better to rob H1!
dp[1] = max($2, $7) = $7
At H2 ($9):
Can skip H2 and keep dp[1] ($7)
OR rob H2 + dp[0] ($9 + $2 = $11)
Better to rob H2!
dp[2] = max($7, $11) = $11
At H3 ($3):
Can skip H3 and keep dp[2] ($11)
OR rob H3 + dp[1] ($3 + $7 = $10)
Better to skip H3!
dp[3] = max($11, $10) = $11
At H4 ($1):
Can skip H4 and keep dp[3] ($11)
OR rob H4 + dp[2] ($1 + $11 = $12)
Better to rob H4!
dp[4] = max($11, $12) = $12 ✓
Build up the answer step by step!
Clear and systematic! 🎯
The Recurrence Relation:
dp[i] = maximum money from houses 0 to i
For house i, we have two choices:
Choice 1: Skip house i
→ Keep the best plan from previous house
→ dp[i-1]
Choice 2: Rob house i
→ Can't use house i-1
→ Must use best plan from house i-2
→ dp[i-2] + nums[i]
Formula:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Base cases:
dp[0] = nums[0] (only one house)
dp[1] = max(nums[0], nums[1]) (pick better of first two)
📝 Implementation
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// Edge cases
if (n == 0) return 0;
if (n == 1) return nums[0];
// Create DP table
int[] dp = new int[n];
// Base cases
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
// Fill table from left to right
for (int i = 2; i < n; i++) {
// Skip house i OR rob house i
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
// Answer is max money from all houses
return dp[n - 1];
}
}
🔍 Detailed Dry Run: nums = [2, 7, 9, 3, 1]
nums = [2, 7, 9, 3, 1]
n = 5
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Create DP table:
dp = [0, 0, 0, 0, 0]
↑ ↑ ↑ ↑ ↑
H0 H1 H2 H3 H4
Base cases:
dp[0] = nums[0] = 2
dp[1] = max(nums[0], nums[1]) = max(2, 7) = 7
dp = [2, 7, 0, 0, 0]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION - Fill table left to right
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Iteration 1: i = 2 (House 2, money = $9)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Choice 1: Skip H2
→ Use dp[1] = $7
Choice 2: Rob H2
→ Use dp[0] + nums[2] = $2 + $9 = $11 ✓
dp[2] = max($7, $11) = $11 ✓
dp = [2, 7, 11, 0, 0]
Meaning: Max money from H0,H1,H2 is $11
Best plan so far: Rob H0($2) + Rob H2($9)
Iteration 2: i = 3 (House 3, money = $3)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Choice 1: Skip H3
→ Use dp[2] = $11 ✓
Choice 2: Rob H3
→ Use dp[1] + nums[3] = $7 + $3 = $10
dp[3] = max($11, $10) = $11 ✓
dp = [2, 7, 11, 11, 0]
Meaning: Max money from H0,H1,H2,H3 is $11
Best plan so far: Still Rob H0($2) + Rob H2($9)
(Skipping H3 is better!)
Iteration 3: i = 4 (House 4, money = $1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Choice 1: Skip H4
→ Use dp[3] = $11
Choice 2: Rob H4
→ Use dp[2] + nums[4] = $11 + $1 = $12 ✓
dp[4] = max($11, $12) = $12 ✓
Final DP table:
dp = [2, 7, 11, 11, 12]
↑ ↑ ↑ ↑ ↑
H0 H1 H2 H3 H4
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT: dp[4] = $12 ✓
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Best plan: Rob H0($2) + Rob H2($9) + Rob H4($1) = $12
How we know the plan:
dp[4] came from dp[2] + nums[4]
→ Robbed H4
dp[2] came from dp[0] + nums[2]
→ Robbed H2
dp[0] = nums[0]
→ Robbed H0
Plan: H0, H2, H4 ✓
Visual DP Table Building:
Position │ House $ │ Skip (dp[i-1]) │ Rob (dp[i-2]+nums[i]) │ Choice │ dp[i]
─────────┼─────────┼────────────────┼───────────────────────┼────────┼──────
0 │ $2 │ N/A │ N/A │ Rob │ $2
1 │ $7 │ $2 │ $7 │ Rob │ $7
2 │ $9 │ $7 │ $2 + $9 │ Rob │ $11
3 │ $3 │ $11 │ $7 + $3 │ Skip │ $11
4 │ $1 │ $11 │ $11 + $1 │ Rob │ $12 ✓
📊 Complexity Analysis
Time Complexity: O(n)
Single loop through houses: O(n)
Constant work at each position: O(1)
Total: O(n) ✓
Space Complexity: O(n)
DP array: O(n)
🔵 Approach 4: Space-Optimized DP (Two Variables Only)
💡 Intuition
The brilliant observation: We only need the last two results!
OBSERVATION:
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
To calculate dp[i], we ONLY need:
- dp[i-1]: previous house result
- dp[i-2]: two houses ago result
We don't need dp[0], dp[1], ... dp[i-3]!
OPTIMIZATION:
Instead of storing entire array:
dp = [2, 7, 11, 11, 12]
Just store two variables:
prev1 = 11 (dp[i-1])
prev2 = 11 (dp[i-2])
Calculate current, then shift:
current = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = current
Save space from O(n) to O(1)! 🚀
Example with Variables:
nums = [2, 7, 9, 3, 1]
Initialize:
prev2 = nums[0] = 2
prev1 = max(nums[0], nums[1]) = max(2, 7) = 7
Process H2 ($9):
current = max(prev1, prev2 + $9)
= max($7, $2 + $9)
= max($7, $11) = $11
Shift: prev2 = 7, prev1 = 11
Process H3 ($3):
current = max(prev1, prev2 + $3)
= max($11, $7 + $3)
= max($11, $10) = $11
Shift: prev2 = 11, prev1 = 11
Process H4 ($1):
current = max(prev1, prev2 + $1)
= max($11, $11 + $1)
= max($11, $12) = $12 ✓
Shift: prev2 = 11, prev1 = 12
Answer: prev1 = $12 ✓
📝 Implementation
class Solution {
public int rob(int[] nums) {
int n = nums.length;
// Edge cases
if (n == 0) return 0;
if (n == 1) return nums[0];
// Only need two variables!
int prev2 = nums[0]; // dp[i-2]
int prev1 = Math.max(nums[0], nums[1]); // dp[i-1]
for (int i = 2; i < n; i++) {
int current = Math.max(prev1, prev2 + nums[i]);
// Shift for next iteration
prev2 = prev1;
prev1 = current;
}
return prev1;
}
}
📊 Complexity Analysis
Time Complexity: O(n)
Same as Approach 3: O(n)
Space Complexity: O(1)
Only two variables: prev1, prev2
No array needed!
Optimal space! ✓
🎯 Pattern Recognition - Choice DP
Core Pattern: Make Optimal Choice at Each Step
Template for "choice" DP problems:
At each position, we have CHOICES:
- Take current element (with consequences)
- Skip current element
Formula:
dp[i] = max/min(
option1_with_current,
option2_without_current
)
For House Robber:
dp[i] = max(
dp[i-2] + nums[i], // Rob this house
dp[i-1] // Skip this house
)
Similar Problems:
- Delete and Earn
- Paint House
- Best Time to Buy/Sell Stock with Cooldown
⚠️ Important Edge Cases to Test
nums = [1,2,3,1] // Expected: 4
nums = [2,7,9,3,1] // Expected: 12
nums = [2,1,1,2] // Expected: 4
nums = [5,3,4,11,2] // Expected: 16
nums = [1] // Expected: 1
nums = [1,2] // Expected: 2
nums = [2,1] // Expected: 2
nums = [5,1,1,5] // Expected: 10
nums = [0,0,0,0] // Expected: 0
nums = [100,1,1,100] // Expected: 200
📝 Quick Revision Notes
🎯 Core Concept
Problem: Rob houses for maximum money without robbing adjacent houses.
Key Insight: At each house, choose to rob it (skip previous) OR skip it (keep previous best).
Four Approaches: 1. Brute Force → Try all combinations, O(2^n) ❌ 2. Top-Down DP → Memoization, O(n), O(n) space ✓ 3. Bottom-Up DP → Tabulation, O(n), O(n) space ✓ 4. Space-Optimized → Two variables, O(n), O(1) space ⭐
⚡ Quick Implementation
import java.util.Arrays;
public class Solution {
public int rob(int[] a) {
// // Approach 1 - recursive
// return recursive(0, a);
// // Approach 2 - top down
// int[] memo = new int[a.length];
// Arrays.fill(memo, -1);
// return topDown(0, a, memo);
// Approach 3 - bottom up
return bottomUp(a);
}
private int bottomUp(int[] a) {
int n = a.length;
if (n < 2) {
return a[0];
}
int[] dp = new int[n];
// base cases
dp[0] = a[0];
dp[1] = Math.max(a[0], a[1]);
for (int i = 2; i < n; i++) {
// option 1 - rob house. So add it and what you got till i-2
// option 2 - skip house. What you got till i-1
// dp[i] => max amount robbed from house number 0 to house number i
dp[i] = Math.max(a[i] + dp[i - 2], dp[i - 1]);
}
return dp[n - 1];
}
private int topDown(int index, int[] a, int[] memo) {
if (index >= a.length) {
return 0;
}
if (memo[index] != -1) {
return memo[index];
}
int robHouse = a[index] + topDown(index + 2, a, memo);
int skipHouse = topDown(index + 1, a, memo);
return memo[index] = Math.max(skipHouse, robHouse);
}
private int recursive(int index, int[] a) {
// Max amount you can rob starting from house no index.
// base case
if (index >= a.length) {
return 0;
}
// option 1 - rob the current house and go to next-to-next house.
int robHouse = a[index] + recursive(index + 2, a);
// option 2 - skip the current house and start from next house itself.
// Note: It does not mean you need to rob next house mandatorily. Function
// definition says what max amount tou can rob starting from house no index+1.
int skipHouse = recursive(index + 1, a);
return Math.max(skipHouse, robHouse);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.rob(new int[] { 1, 2, 3, 1 }) == 4);
System.out.println(s.rob(new int[] { 2, 7, 9, 3, 1 }) == 12);
}
}
// Approach 4: Space-Optimized (Best!)
public int rob(int[] nums) {
if (nums.length == 0) return 0;
if (nums.length == 1) return nums[0];
int prev2 = nums[0];
int prev1 = Math.max(nums[0], nums[1]);
for (int i = 2; i < nums.length; i++) {
int current = Math.max(prev1, prev2 + nums[i]);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
🔑 Key Insights
The Two Choices:
At house i:
Choice 1: Rob it
→ Get nums[i] money
→ Must skip house i-1
→ Use best plan from i-2: dp[i-2] + nums[i]
Choice 2: Skip it
→ Get 0 from house i
→ Can use best plan from i-1: dp[i-1]
Take whichever gives more money!
Why This Works:
dp[i] = best money from houses 0 to i
If we rob house i:
We MUST have skipped house i-1
So we can use dp[i-2]
If we skip house i:
We can use whatever was best for i-1
So we use dp[i-1]
max(both options) = optimal!
Space Optimization:
Only need last two values:
prev1 = dp[i-1]
prev2 = dp[i-2]
Calculate current, shift values:
current = max(prev1, prev2 + nums[i])
prev2 = prev1
prev1 = current
From O(n) space to O(1)! 🚀
🎪 Memory Aid
"Rob or skip - choose wisely!"
"Can't rob neighbors - police alarm!"
"Only need last two houses!"
"Build fortune house by house!" ✨
⚠️ Common Mistakes
- ❌ Forgetting base cases (n=0, n=1)
- ❌ Not handling edge case when n=1
- ❌ Using dp[i-1] and dp[i-2] without checking bounds
- ❌ Thinking greedy works (it doesn't always!)
- ❌ Not initializing dp[1] correctly
✅ Interview Talking Points
"This is a classic DP problem with choices.
Intuition:
At each house, we face a choice:
- Rob it (get money, skip next)
- Skip it (keep previous best)
Approach (Bottom-Up):
1. Base cases:
- dp[0] = nums[0] (only one house)
- dp[1] = max(nums[0], nums[1]) (pick better)
2. For each house i from 2 to n-1:
- Option 1: Skip it → dp[i-1]
- Option 2: Rob it → dp[i-2] + nums[i]
- dp[i] = max(both options)
3. Return dp[n-1]
Optimization:
We only need last two values (dp[i-1] and dp[i-2])
Use two variables instead of array
Reduces space from O(n) to O(1)
Complexity: O(n) time, O(1) space
This is optimal!"
🎉 Congratulations!
You've mastered House Robber - a classic DP problem!
What You Learned:
✅ Choice DP - Optimal decision at each step
✅ Adjacent Constraint - Can't take neighbors
✅ Bottom-Up Building - Build solution incrementally
✅ Space Optimization - From O(n) to O(1)
✅ Two Variables Trick - Only need last two values
✅ Recurrence Relations - max(skip, rob)
You've mastered a fundamental DP pattern! 🚀✨