📚 Table of Contents
📋 Problem Statement
Given non-negative integers representing money in each house, maximize stolen money with the rule: you cannot choose two neighboring indices.
Examples
Example 1:
Rob houses 1 and 3: 1 + 3 = 4.
Input: [1,2,3,1]Output: 4Rob houses 1 and 3: 1 + 3 = 4.
Example 2:
Rob houses 1, 3, 5 style choice: 2 + 9 + 1 = 12.
Input: [2,7,9,3,1]Output: 12Rob houses 1, 3, 5 style choice: 2 + 9 + 1 = 12.
🎯 Real-World Analogy
Choosing Non-Adjacent Time Slots
You have paid meetings in a timeline but cannot attend back-to-back slots. At each slot, decide: take this one (skip previous) or skip this one (keep previous best).
💡 Key Insights
- State: best up to index i depends only on i-1 and i-2.
- Transition:
dp[i] = max(dp[i-1], dp[i-2] + nums[i]). - Either skip current house or rob current house.
- Only two previous states are needed, so O(1) extra space.
💻 Solution Approaches
Approach 1: Top-Down Memoization
Time: O(N) | Space: O(N)
Approach 2: Bottom-Up O(1) Space (Recommended)
Time: O(N) | Space: O(1)
Python Implementation
from typing import List
def rob(nums: List[int]) -> int:
prev2 = 0 # best up to i-2
prev1 = 0 # best up to i-1
for value in nums:
take = prev2 + value
skip = prev1
current = max(take, skip)
prev2 = prev1
prev1 = current
return prev1
JavaScript Implementation
function rob(nums) {
let prev2 = 0;
let prev1 = 0;
for (const value of nums) {
const take = prev2 + value;
const skip = prev1;
const current = Math.max(take, skip);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
🔍 Step-by-Step Walkthrough
Trace [2,7,9,3,1]:
Start: prev2=0, prev1=0
2 -> max(0+2,0)=2
7 -> max(0+7,2)=7
9 -> max(2+9,7)=11
3 -> max(7+3,11)=11
1 -> max(11+1,11)=12
⚡ Complexity Analysis
Time: O(N) because each house is processed once.
Space: O(1) using two rolling states.
🔧 Edge Cases
- Empty input -> 0
- Single house -> that value
- Two houses -> max of two
- All zeros -> 0
- Large values to ensure no adjacency violations
🧪 Test Cases
Python
def test_rob():
assert rob([1,2,3,1]) == 4
assert rob([2,7,9,3,1]) == 12
assert rob([]) == 0
assert rob([5]) == 5
assert rob([2,1,1,2]) == 4
print("✅ all tests passed")JavaScript
function testRob() {
console.assert(rob([1,2,3,1]) === 4, "test 1");
console.assert(rob([2,7,9,3,1]) === 12, "test 2");
console.assert(rob([]) === 0, "test 3");
console.log("✅ all tests passed");
}💼 Interview Tips
- Say the state transition aloud before coding.
- Mention relation to max non-adjacent subsequence pattern.
- Show O(1)-space refinement after DP-array explanation.
🎓 Key Takeaways
- DP is choosing between "take" and "skip" at each index.
- Rolling variables are enough for linear-time solution.