Builds on Linear DP, which you haven’t finished yet.
House Robber (Non-Adjacent Maximum Sum)
i rules out item i - 1, so the recurrence becomes dp[i] = max(dp[i - 1], dp[i - 2] + x).House Robber (LC 198)(opens leetcode.com)
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.
House Robber
dp[i] = max(dp[i-1], dp[i-2] + x) ➔ skip a house or rob it on top of the best from two back ➔ O(1) rolling registers| 1 | def rob(nums: list[int]) -> int: |
| 2 | """House Robber: Non-adjacent maximum sum using O(1) rolling space. |
| 3 | Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) |
| 4 | Time: O(N) | Space: O(1) |
| 5 | """ |
| 6 | if not nums: |
| 7 | return 0 |
| 8 | |
| 9 | # prev2, prev1: rolling dp[i-2] and dp[i-1], the best totals two and one house back |
| 10 | prev2, prev1 = 0, 0 |
| 11 | for x in nums: |
| 12 | # 1. Decide This House: |
| 13 | # Skip it and keep prev1, or rob it on top of the best total from two houses back (prev2 + x). |
| 14 | curr = max(prev1, prev2 + x) |
| 15 | |
| 16 | # 2. Roll The Window Forward: |
| 17 | # Shift prev2 to the old prev1 before overwriting prev1, since prev1 is still needed for prev2's new value. |
| 18 | prev2 = prev1 |
| 19 | prev1 = curr |
| 20 | |
| 21 | return prev1 |
x, prev1 is the best total for the houses seen so far and prev2 is the best total without the last of them.Each answer depends only on the last one or two answers: at every house you either skip it (prev1) or rob it on top of the best from two houses back (prev2 + x). So the whole dp table collapses into two rolling variables that shift forward once per item. Shift in the right order, curr first, then prev2 = prev1, then prev1 = curr, or you overwrite a value you still need.
See it run
House Robber, step by step
prev2 0prev1 0
Each column is one house. Each cell in the dp row is the best total so far.
xthe house being readprev1the best total up to the previous house (skip this house)prev2the best total up to two houses back (rob this house)currthe new best total after this house
Start: prev2 = 0 and prev1 = 0. Zero houses give a total of 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Setting
prev1 = currbeforeprev2 = prev1Mistakeprev1 = curr prev2 = prev1Fixprev2 = prev1 prev1 = currWhat happens:
prev1holdsdp[i-1]andprev2holdsdp[i-2]. The nextdp[i-2]is the oldprev1. Ifprev1 = currruns first, that old value is lost. Thenprev2 = prev1copiescurr, so both variables hold the same value.Example: nums = [2, 7, 9, 3, 1]Mistake: returns 22Fix: returns 12
- One locally best move at each index can never hurt a later one, as in Jump Game (LC 55): there are no earlier answers to weigh against each other. See Greedy
- Each day you are in one of several modes (holding a stock or not) with rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): one number per index can't say which mode you are in. See State Machine DP
Deep Dive
Why dp[i] = max(dp[i - 1], dp[i - 2] + x) is correct
Here dp[i] is the best total you can take from the first i houses. No two chosen houses may be next to each other.
Look at the last house, with value x. There are only two cases. In the first case, you skip it. Then the best total is the best total for the first i - 1 houses, which is dp[i - 1].
In the second case, you rob it. Then the previous house must be skipped, so the rest comes from the first i - 2 houses. The best total is dp[i - 2] + x.
The answer is the larger of the two. Every valid choice falls into one of these cases, so no choice is missed.
Example: for nums = [2, 7, 9, 3, 1], the answer is 12. It is the sum of houses 2, 9 and 1.
What this card adds to Linear DP
Linear DP counts paths and adds two answers. This card makes a choice with max. The loop, the two rolling variables and the shift order stay the same.
The starting values are prev2, prev1 = 0, 0. They mean that zero houses give a total of 0. The loop then starts at the first house, and not at index 2.
The word "best so far" is exact here. prev1 is the best total for all houses seen, not the best total that ends at the last house. This matters, as the next section shows.
Trace and the cost
Trace for nums = [2, 7, 9, 3, 1]. Each row shows x, then prev1 (skip), then prev2 + x (rob), then curr:
x = 2: skip 0, rob 2,curr = 2.x = 7: skip 2, rob 7,curr = 7.x = 9: skip 7, rob 11,curr = 11.x = 3: skip 11, rob 10,curr = 11.x = 1: skip 11, rob 12,curr = 12.
There are N states and each does one max. The time is O(N) and the space is O(1).
The same code works for a table of N values with constraints on neighbours only. It does not work when a choice also blocks houses far away.
Why simple rules fail
Two simple ideas look right and are wrong. The first is to take the largest house, remove its neighbours, and repeat. For [5, 6, 5], this takes 6 and returns 6. The answer is 10, from the two houses of value 5.
The second is to compare the sum of the even positions with the sum of the odd positions. For [2, 1, 1, 2], both sums are 3. The answer is 4, from the first and the last house.
A locally best choice can block a better pair. The recurrence works because it compares both complete choices at each house.
60-Second Pitch
"At each house I have two choices. I skip it and keep the best total so far, or I rob it and add its value to the best total from two houses back. I take the larger one. That gives dp[i] = max(dp[i - 1], dp[i - 2] + x). It reads only two earlier answers, so I use prev1 and prev2. The time is O(N) and the space is O(1). For a circle of houses, the first and last houses touch. I run the same function twice, once without the first house and once without the last, and take the maximum."
Common Questions
- Why is the greedy rule "take the largest house" wrong?
The largest house can block two good neighbours. For
[5, 6, 5], the greedy rule takes 6 and returns 6. The correct answer is 10, from the two houses of value 5. The recurrence compares both complete choices at every house, so it does not make this mistake.- How do you solve House Robber II (LC 213), where the houses form a circle?
The first and last houses touch, so you cannot rob both. Run
robonnums[1:], which skips the first house, and onnums[:-1], which skips the last house. Return the larger result. For[2, 3, 2], the answer is 3. If there is one house, return its value, because both slices are empty.- What is the time and space complexity of
rob? O(N)time, because each house does onemax.O(1)space, because onlyprev1,prev2andcurrexist.- How does Delete and Earn (LC 740) use this card?
Add up the points for each value. Taking value
vremovesv - 1andv + 1, so neighbouring values cannot both be taken. Lay out the sums by value, from the smallest to the largest value, with zero for missing values. Then runrobon that list.- How do you return the chosen houses and not only the total?
Keep a full
dptable and walk back from the end. At housei, ifdp[i] == dp[i - 1], houseiwas skipped. Otherwise, houseiwas robbed, and you continue fromi - 2. This needsO(N)space.
SWE Reasoning
Spot it
- Items are in a line, and you choose a subset to maximise a total.
- Two chosen items may not be neighbours.
- A greedy rule, such as "take the biggest", fails on a small example like
[5, 6, 5]. - The answer for the first
iitems depends only on the answers for the firsti - 1andi - 2items. - Values are not negative, so skipping an item is always allowed and taking it never hurts.
The invariant, step by step
- Before the loop,
prev2andprev1are both 0. No house has been seen, so the best total is 0. - For the next house with value
x,prev1is the best total for all houses before it.prev2is the best total without the last of them. - Skipping the house keeps the total
prev1. Robbing it givesprev2 + x, because its left neighbour is skipped. curr = max(prev1, prev2 + x)is the best total for the houses up to and including this one.prev2 = prev1runs first, thenprev1 = curr. The invariant holds for the next house.- After the last house,
prev1is the best total for all houses.
Traps
- Wrong shift order. If
prev1 = currruns first, both variables holdcurr. For[2, 7, 9, 3, 1], the result is 22 instead of 12. - Best ending here, not best so far.
curr = prev2 + xforgets the skip case. For[2, 1, 1, 2], the result is 3 instead of 4. - Circle of houses. In House Robber II (LC 213), the first and last houses are neighbours.
rob(nums)can take both. Runrobonnums[1:]and onnums[:-1], and return the larger result. Handle one house on its own. - Empty list. The blueprint returns 0 for an empty list. Without that check, a version that reads
nums[0]raisesIndexError. - Hidden extra rule. If the problem also blocks values far away, the two-back rule is not enough. Change the state before you reuse this code.
Practice
Builds on Linear DP, which you haven’t finished yet.
House Robber (Non-Adjacent Maximum Sum)
i rules out item i - 1, so the recurrence becomes dp[i] = max(dp[i - 1], dp[i - 2] + x).House Robber (LC 198)(opens leetcode.com)
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.
House Robber
dp[i] = max(dp[i-1], dp[i-2] + x) ➔ skip a house or rob it on top of the best from two back ➔ O(1) rolling registers| 1 | def rob(nums: list[int]) -> int: |
| 2 | """House Robber: Non-adjacent maximum sum using O(1) rolling space. |
| 3 | Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) |
| 4 | Time: O(N) | Space: O(1) |
| 5 | """ |
| 6 | if not nums: |
| 7 | return 0 |
| 8 | |
| 9 | # prev2, prev1: rolling dp[i-2] and dp[i-1], the best totals two and one house back |
| 10 | prev2, prev1 = 0, 0 |
| 11 | for x in nums: |
| 12 | # 1. Decide This House: |
| 13 | # Skip it and keep prev1, or rob it on top of the best total from two houses back (prev2 + x). |
| 14 | curr = max(prev1, prev2 + x) |
| 15 | |
| 16 | # 2. Roll The Window Forward: |
| 17 | # Shift prev2 to the old prev1 before overwriting prev1, since prev1 is still needed for prev2's new value. |
| 18 | prev2 = prev1 |
| 19 | prev1 = curr |
| 20 | |
| 21 | return prev1 |
x, prev1 is the best total for the houses seen so far and prev2 is the best total without the last of them.Each answer depends only on the last one or two answers: at every house you either skip it (prev1) or rob it on top of the best from two houses back (prev2 + x). So the whole dp table collapses into two rolling variables that shift forward once per item. Shift in the right order, curr first, then prev2 = prev1, then prev1 = curr, or you overwrite a value you still need.
See it run
House Robber, step by step
prev2 0prev1 0
Each column is one house. Each cell in the dp row is the best total so far.
xthe house being readprev1the best total up to the previous house (skip this house)prev2the best total up to two houses back (rob this house)currthe new best total after this house
Start: prev2 = 0 and prev1 = 0. Zero houses give a total of 0.
Gotcha 1 of 3
- The trap
Gotcha 1: Setting
prev1 = currbeforeprev2 = prev1Mistakeprev1 = curr prev2 = prev1Fixprev2 = prev1 prev1 = currWhat happens:
prev1holdsdp[i-1]andprev2holdsdp[i-2]. The nextdp[i-2]is the oldprev1. Ifprev1 = currruns first, that old value is lost. Thenprev2 = prev1copiescurr, so both variables hold the same value.Example: nums = [2, 7, 9, 3, 1]Mistake: returns 22Fix: returns 12
- One locally best move at each index can never hurt a later one, as in Jump Game (LC 55): there are no earlier answers to weigh against each other. See Greedy
- Each day you are in one of several modes (holding a stock or not) with rules for moving between them, as in Best Time to Buy and Sell Stock with Transaction Fee (LC 714): one number per index can't say which mode you are in. See State Machine DP
Deep Dive
Why dp[i] = max(dp[i - 1], dp[i - 2] + x) is correct
Here dp[i] is the best total you can take from the first i houses. No two chosen houses may be next to each other.
Look at the last house, with value x. There are only two cases. In the first case, you skip it. Then the best total is the best total for the first i - 1 houses, which is dp[i - 1].
In the second case, you rob it. Then the previous house must be skipped, so the rest comes from the first i - 2 houses. The best total is dp[i - 2] + x.
The answer is the larger of the two. Every valid choice falls into one of these cases, so no choice is missed.
Example: for nums = [2, 7, 9, 3, 1], the answer is 12. It is the sum of houses 2, 9 and 1.
What this card adds to Linear DP
Linear DP counts paths and adds two answers. This card makes a choice with max. The loop, the two rolling variables and the shift order stay the same.
The starting values are prev2, prev1 = 0, 0. They mean that zero houses give a total of 0. The loop then starts at the first house, and not at index 2.
The word "best so far" is exact here. prev1 is the best total for all houses seen, not the best total that ends at the last house. This matters, as the next section shows.
Trace and the cost
Trace for nums = [2, 7, 9, 3, 1]. Each row shows x, then prev1 (skip), then prev2 + x (rob), then curr:
x = 2: skip 0, rob 2,curr = 2.x = 7: skip 2, rob 7,curr = 7.x = 9: skip 7, rob 11,curr = 11.x = 3: skip 11, rob 10,curr = 11.x = 1: skip 11, rob 12,curr = 12.
There are N states and each does one max. The time is O(N) and the space is O(1).
The same code works for a table of N values with constraints on neighbours only. It does not work when a choice also blocks houses far away.
Why simple rules fail
Two simple ideas look right and are wrong. The first is to take the largest house, remove its neighbours, and repeat. For [5, 6, 5], this takes 6 and returns 6. The answer is 10, from the two houses of value 5.
The second is to compare the sum of the even positions with the sum of the odd positions. For [2, 1, 1, 2], both sums are 3. The answer is 4, from the first and the last house.
A locally best choice can block a better pair. The recurrence works because it compares both complete choices at each house.
60-Second Pitch
"At each house I have two choices. I skip it and keep the best total so far, or I rob it and add its value to the best total from two houses back. I take the larger one. That gives dp[i] = max(dp[i - 1], dp[i - 2] + x). It reads only two earlier answers, so I use prev1 and prev2. The time is O(N) and the space is O(1). For a circle of houses, the first and last houses touch. I run the same function twice, once without the first house and once without the last, and take the maximum."
Common Questions
- Why is the greedy rule "take the largest house" wrong?
The largest house can block two good neighbours. For
[5, 6, 5], the greedy rule takes 6 and returns 6. The correct answer is 10, from the two houses of value 5. The recurrence compares both complete choices at every house, so it does not make this mistake.- How do you solve House Robber II (LC 213), where the houses form a circle?
The first and last houses touch, so you cannot rob both. Run
robonnums[1:], which skips the first house, and onnums[:-1], which skips the last house. Return the larger result. For[2, 3, 2], the answer is 3. If there is one house, return its value, because both slices are empty.- What is the time and space complexity of
rob? O(N)time, because each house does onemax.O(1)space, because onlyprev1,prev2andcurrexist.- How does Delete and Earn (LC 740) use this card?
Add up the points for each value. Taking value
vremovesv - 1andv + 1, so neighbouring values cannot both be taken. Lay out the sums by value, from the smallest to the largest value, with zero for missing values. Then runrobon that list.- How do you return the chosen houses and not only the total?
Keep a full
dptable and walk back from the end. At housei, ifdp[i] == dp[i - 1], houseiwas skipped. Otherwise, houseiwas robbed, and you continue fromi - 2. This needsO(N)space.
SWE Reasoning
Spot it
- Items are in a line, and you choose a subset to maximise a total.
- Two chosen items may not be neighbours.
- A greedy rule, such as "take the biggest", fails on a small example like
[5, 6, 5]. - The answer for the first
iitems depends only on the answers for the firsti - 1andi - 2items. - Values are not negative, so skipping an item is always allowed and taking it never hurts.
The invariant, step by step
- Before the loop,
prev2andprev1are both 0. No house has been seen, so the best total is 0. - For the next house with value
x,prev1is the best total for all houses before it.prev2is the best total without the last of them. - Skipping the house keeps the total
prev1. Robbing it givesprev2 + x, because its left neighbour is skipped. curr = max(prev1, prev2 + x)is the best total for the houses up to and including this one.prev2 = prev1runs first, thenprev1 = curr. The invariant holds for the next house.- After the last house,
prev1is the best total for all houses.
Traps
- Wrong shift order. If
prev1 = currruns first, both variables holdcurr. For[2, 7, 9, 3, 1], the result is 22 instead of 12. - Best ending here, not best so far.
curr = prev2 + xforgets the skip case. For[2, 1, 1, 2], the result is 3 instead of 4. - Circle of houses. In House Robber II (LC 213), the first and last houses are neighbours.
rob(nums)can take both. Runrobonnums[1:]and onnums[:-1], and return the larger result. Handle one house on its own. - Empty list. The blueprint returns 0 for an empty list. Without that check, a version that reads
nums[0]raisesIndexError. - Hidden extra rule. If the problem also blocks values far away, the two-back rule is not enough. Change the state before you reuse this code.