House Robber (LeetCode 198)
Houses stand in a row, each holding a known amount of cash, but any two houses sitting right next to each other share a single alarm, so burgling both in one night sets it off.
Given the stash in each house as nums, find the largest total you can collect in one night without ever choosing two adjacent houses.
Worked Examples
nums = [1,2,3,1]4nums = [2,7,9,3,1]12⚖️Formal Constraints & Bounds
1 <= nums.length <= 1000 <= nums[i] <= 400
Core Insight
Transitions only look back two steps (i - 1 and i - 2). Keeping two scalar variables prev1 and prev2 eliminates the O(N) array allocation entirely.
Real-World Scenario & Production Applications
Resource scheduling with refractory cooldowns, portfolio rebalancing with mandatory cooldown intervals, and adjacent security sensor constraints.
Subproblems & Recurrence Decomposition3 Phases
Let prev2 = 0 (the best total up to two houses back) and prev1 = 0 (the best total up to the previous house).
# Base State: 2 rolling scalar registers
prev2 = 0 # Max loot up to house i - 2
prev1 = 0 # Max loot up to house i - 1Step-by-Step Execution Trace Table
House i | House Value | Option A: Skip (prev1) | Option B: Rob (money + prev2) | Chosen dp[i] | Rationale |
|---|---|---|---|---|---|
| 0 | 2 | — | 2 + 0 = 2 | 2 | Rob house 0. |
| 1 | 7 | 2 | 7 + 0 = 7 | 7 | Rob house 1 (beats house 0). |
| 2 | 9 | 7 | 9 + 2 = 11 | 11 | Rob house 2 + house 0. |
| 3 | 3 | 11 | 3 + 7 = 10 | 11 | Skip house 3 (11 > 10), preserving house 4 option! |
| 4 | 1 | 11 | 1 + 11 = 12 | 12 | Rob house 4 + house 2 + house 0 Max = 12. |
| 1 | if not nums: |
| 2 | return 0 |
| 3 | prev2, prev1 = 0, 0 |
| 4 | for x in nums: |
| 5 | curr = max(prev1, prev2 + x) |
| 6 | prev2 = prev1 |
| 7 | prev1 = curr |
| 8 | return prev1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
House Robber enforces a non-consecutive constraint: adjacent houses trigger alarms. At each house $i$, we face a binary decision: rob house $i$ (yielding $nums[i]$ plus the optimal loot from house $i-2$) or skip house $i$ (retaining the optimal loot from house $i-1$). The recurrence $dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$ depends only on two previous states, enabling $O(N)$ runtime with $O(1)$ scalar memory. 🏠 The Analogy: Two Running Totals, One Step Apart
Walk down the street holding two running numbers in your head: "the best I could do up through the previous house" and "the best I could do up through the house before that." At each new house, you have exactly two options: skip it (your total stays whatever the previous house's best was), or rob it (add this house's stash to whatever the best was two houses back, since robbing this one forces you to have skipped the one right before it). Take whichever option is bigger, then shift both running numbers forward by one house.
🔑 The Key Idea in the Code
Only two numbers ever need to be carried forward — not an array of every house's best score — because the decision at any house only ever needs "best up to one house back" and "best up to two houses back," nothing further.
Greedy even vs odd alternating choice is flawed: Robbing all even indices or all odd indices is not optimal. Counterexample:
[2, 1, 1, 2]yields , whereas even sum is 3 and odd sum is 3. DP is required.A one-house street: an array-based solution that seeds
dp[1] = max(nums[0], nums[1])reads past the end whenlen(nums) == 1; returnnums[0]first, or use the two rolling variables, which need no seeding.Believing you need to check
dp[i-3]: Skipping two consecutive houses is never optimal because you could have safely robbed the intermediate house without conflict. Recurrencemax(prev1, prev2 + num)is strictly sufficient.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Maximum sum of non-adjacent elements" + 1D sequential choices with refractory cooldown.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Invariant: prev1 stores max profit up to house i-1, prev2 stores max profit up to house i-2.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Shift in the right order: compute
currfrom the old values, thenprev2 = prev1, thenprev1 = curr. Writingprev1 = currfirst makesprev2a copy of the new value, so the next house is added on top of its own neighbour.Greedy picks fail: taking every other house (all even or all odd positions) gives 3 on
[2, 1, 1, 2], but robbing the two ends gives 4. Only comparing skip (prev1) with rob (prev2 + x) at every house finds it.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Linear DP. The best total up to a house depends only on the best totals up to the two houses before it, so I don't need a whole table. I keep two numbers: prev1, the best total up to the previous house, and prev2, the best total up to the house before that. At each house I compare two choices: skip it and keep prev1, or rob it and add its money to prev2, because robbing it rules out its neighbour. The larger one is curr, the best total so far. Both numbers already hold the best answer for their part of the street, so these two choices are the only ones I need. The trap is the shift order: I compute curr from the old values first, then move prev1 into prev2 and curr into prev1; overwriting prev1 first would let me rob two neighbours. One pass, so
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Maintains two rolling variables (prev1, prev2) for maximum loot up to the previous two houses. Single linear pass.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores 2 scalar integer registers in O(1) space.
T(N) = N · O(1) = O(N)
Derivation Progression
curr = max(prev1, prev2 + x)
Optimal choice is max of skipping current house or robbing it.
prev2, prev1 = prev1, curr
Shifts window forward in O(1).
N house evaluations = O(N)
Computes max profit in single linear pass.
Variable Definitions
Total number of houses along the street
Memory Architecture & Bounds
O(1) Iterative
O(1) Two integer registers
O(1) Maximum loot integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "cannot rob adjacent houses", "maximize the amount of money". Binary include/exclude decision at each element: rob current house () OR skip current house ().
. Time budget . Space budget .
Streams: after each house, prev1 is already the best total for the houses seen so far, so the same two variables answer the question for houses arriving one at a time, with O(1) memory and no second pass. The largest possible answer here is 100 × 400 = 40,000, so overflow is not a concern.
House Robber (LeetCode 198)
Houses stand in a row, each holding a known amount of cash, but any two houses sitting right next to each other share a single alarm, so burgling both in one night sets it off.
Given the stash in each house as nums, find the largest total you can collect in one night without ever choosing two adjacent houses.
Worked Examples
nums = [1,2,3,1]4nums = [2,7,9,3,1]12⚖️Formal Constraints & Bounds
1 <= nums.length <= 1000 <= nums[i] <= 400
Core Insight
Transitions only look back two steps (i - 1 and i - 2). Keeping two scalar variables prev1 and prev2 eliminates the O(N) array allocation entirely.
Real-World Scenario & Production Applications
Resource scheduling with refractory cooldowns, portfolio rebalancing with mandatory cooldown intervals, and adjacent security sensor constraints.
Subproblems & Recurrence Decomposition3 Phases
Let prev2 = 0 (the best total up to two houses back) and prev1 = 0 (the best total up to the previous house).
# Base State: 2 rolling scalar registers
prev2 = 0 # Max loot up to house i - 2
prev1 = 0 # Max loot up to house i - 1Step-by-Step Execution Trace Table
House i | House Value | Option A: Skip (prev1) | Option B: Rob (money + prev2) | Chosen dp[i] | Rationale |
|---|---|---|---|---|---|
| 0 | 2 | — | 2 + 0 = 2 | 2 | Rob house 0. |
| 1 | 7 | 2 | 7 + 0 = 7 | 7 | Rob house 1 (beats house 0). |
| 2 | 9 | 7 | 9 + 2 = 11 | 11 | Rob house 2 + house 0. |
| 3 | 3 | 11 | 3 + 7 = 10 | 11 | Skip house 3 (11 > 10), preserving house 4 option! |
| 4 | 1 | 11 | 1 + 11 = 12 | 12 | Rob house 4 + house 2 + house 0 Max = 12. |
| 1 | if not nums: |
| 2 | return 0 |
| 3 | prev2, prev1 = 0, 0 |
| 4 | for x in nums: |
| 5 | curr = max(prev1, prev2 + x) |
| 6 | prev2 = prev1 |
| 7 | prev1 = curr |
| 8 | return prev1 |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
House Robber enforces a non-consecutive constraint: adjacent houses trigger alarms. At each house $i$, we face a binary decision: rob house $i$ (yielding $nums[i]$ plus the optimal loot from house $i-2$) or skip house $i$ (retaining the optimal loot from house $i-1$). The recurrence $dp[i] = \max(dp[i-1], dp[i-2] + nums[i])$ depends only on two previous states, enabling $O(N)$ runtime with $O(1)$ scalar memory. 🏠 The Analogy: Two Running Totals, One Step Apart
Walk down the street holding two running numbers in your head: "the best I could do up through the previous house" and "the best I could do up through the house before that." At each new house, you have exactly two options: skip it (your total stays whatever the previous house's best was), or rob it (add this house's stash to whatever the best was two houses back, since robbing this one forces you to have skipped the one right before it). Take whichever option is bigger, then shift both running numbers forward by one house.
🔑 The Key Idea in the Code
Only two numbers ever need to be carried forward — not an array of every house's best score — because the decision at any house only ever needs "best up to one house back" and "best up to two houses back," nothing further.
Greedy even vs odd alternating choice is flawed: Robbing all even indices or all odd indices is not optimal. Counterexample:
[2, 1, 1, 2]yields , whereas even sum is 3 and odd sum is 3. DP is required.A one-house street: an array-based solution that seeds
dp[1] = max(nums[0], nums[1])reads past the end whenlen(nums) == 1; returnnums[0]first, or use the two rolling variables, which need no seeding.Believing you need to check
dp[i-3]: Skipping two consecutive houses is never optimal because you could have safely robbed the intermediate house without conflict. Recurrencemax(prev1, prev2 + num)is strictly sufficient.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"Maximum sum of non-adjacent elements" + 1D sequential choices with refractory cooldown.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Recurrence: dp[i] = max(dp[i-1], nums[i] + dp[i-2]). Invariant: prev1 stores max profit up to house i-1, prev2 stores max profit up to house i-2.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Shift in the right order: compute
currfrom the old values, thenprev2 = prev1, thenprev1 = curr. Writingprev1 = currfirst makesprev2a copy of the new value, so the next house is added on top of its own neighbour.Greedy picks fail: taking every other house (all even or all odd positions) gives 3 on
[2, 1, 1, 2], but robbing the two ends gives 4. Only comparing skip (prev1) with rob (prev2 + x) at every house finds it.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'd use Linear DP. The best total up to a house depends only on the best totals up to the two houses before it, so I don't need a whole table. I keep two numbers: prev1, the best total up to the previous house, and prev2, the best total up to the house before that. At each house I compare two choices: skip it and keep prev1, or rob it and add its money to prev2, because robbing it rules out its neighbour. The larger one is curr, the best total so far. Both numbers already hold the best answer for their part of the street, so these two choices are the only ones I need. The trap is the shift order: I compute curr from the old values first, then move prev1 into prev2 and curr into prev1; overwriting prev1 first would let me rob two neighbours. One pass, so
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Maintains two rolling variables (prev1, prev2) for maximum loot up to the previous two houses. Single linear pass.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only stores 2 scalar integer registers in O(1) space.
T(N) = N · O(1) = O(N)
Derivation Progression
curr = max(prev1, prev2 + x)
Optimal choice is max of skipping current house or robbing it.
prev2, prev1 = prev1, curr
Shifts window forward in O(1).
N house evaluations = O(N)
Computes max profit in single linear pass.
Variable Definitions
Total number of houses along the street
Memory Architecture & Bounds
O(1) Iterative
O(1) Two integer registers
O(1) Maximum loot integer
Boundary Best / Worst Cases
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "cannot rob adjacent houses", "maximize the amount of money". Binary include/exclude decision at each element: rob current house () OR skip current house ().
. Time budget . Space budget .
Streams: after each house, prev1 is already the best total for the houses seen so far, so the same two variables answer the question for houses arriving one at a time, with O(1) memory and no second pass. The largest possible answer here is 100 × 400 = 40,000, so overflow is not a concern.