The problem
Houses along a street hold some money. You can’t rob two neighbouring houses (an alarm would go off). What is the most money you can take?
Input: [2, 7, 9, 3, 1] Output: 12 (2 + 9 + 1)
Picture it
Picture a burglar walking down a street of houses. At each house they decide: rob it (add its loot to the best total from two houses back) or skip it (keep the best total from the previous house). We keep two running totals and pick the better each time.
How to recognise it
- You pick items from a line to maximise a total, under a rule that forbids neighbours (no two adjacent houses).
- Every decision is yes or no for one house, and the choice at house i only interacts with house i − 1.
- The best total up to house i can be built from the best totals up to the previous one or two houses.
- Up to 100 houses (money at most 400) is far too many to try every subset: there are 2^100 of them.
- "Choose a non-conflicting set with the largest value" on a line is the classic 1-D dynamic programming (DP) shape.
Start with brute force
For each house you have two options: skip it and look at the rest, or rob it and jump over its neighbour. Try both and keep the larger.
def rob_brute(houses):
def go(i): # best loot from houses[i:]
if i >= len(houses):
return 0
return max(go(i + 1), houses[i] + go(i + 2))
return go(0)
This is correct, but each call makes up to two more, so time is exponential (about O(1.6^n)); for 100 houses that is more than 10^20 calls. The same suffixes are solved again and again. Space is O(n) for the recursion.
From brute force to the idea
- Find the waste.
go(5)is reached fromgo(4)(skipped house 4) and fromgo(3)(robbed house 3). Its answer never changes, yet it is recomputed. - Define two running answers. After looking at some houses, track
skip, the best total when the latest house is not robbed, andtake, the best total when it is robbed. - Update both from the old values. For the next house with
loot: the newskipis the better of the old two (the latest house is skipped either way), and the newtakeis the oldskipplusloot(robbing it needs its neighbour untouched). - Answer. After the last house,
max(skip, take).
This is the key idea: the best total after each house depends only on two numbers, so you need two variables, not a table.
Note the single line skip, take = max(skip, take), skip + loot: Python builds the right side from the old values first. That order matters.
The key idea
best[i] = max(best[i − 1], best[i − 2] + money[i]). O(n), O(1) memory.
Python solution
def rob(houses):
skip, take = 0, 0 # best total if the last house was skipped / robbed
for loot in houses:
skip, take = max(skip, take), skip + loot
return max(skip, take)In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(1.6^n): two branches per house, suffixes re-solved | O(n): recursion depth |
| Two variables (shown code) | O(n): one pass, two operations per house | O(1): only skip and take |
Edge cases
- No houses (
[]): returns0. - One house (
[5]): returns5. - Two houses (
[2, 1]): returns2, the larger one, since they are neighbours. - Example
[1, 2, 3, 1]: returns4(houses 1 and 3). - Example
[2, 7, 9, 3, 1]: returns12. - Zeros (
[0, 0]): returns0. - Big loot is not at the ends (
[3, 10, 3, 1, 2]): returns12; the 10 and the 2 beat 3 + 3 + 2.
Common mistakes
- Greedily robbing the biggest house first: in
[2, 1, 1, 2]that is not the best plan (the answer 4 takes both 2s). - Updating
skipfirst and then computingtakefrom the newskip. That lets you rob two neighbours (see the quiz). - Returning
takealone, which is wrong when the last house is better skipped (for[2, 1]it gives 1). - Using
take + loot, which adds every house together and ignores the neighbour rule.
Now robbing house i also sets off the alarm for houses two away, so any two robbed houses must be at least three positions apart (indices differ by 3 or more). Find the most money. For [3, 1, 1, 3] the answer is 6. Describe your approach, then write it if you like.
Compare with our answer
The earlier winner now has to come from three houses back when you rob the current one.
def rob_gap(houses):
n = len(houses)
best = [0] * (n + 1) # best[i]: most loot from the first i houses
for i in range(1, n + 1):
best[i] = max(best[i - 1], best[max(i - 3, 0)] + houses[i - 1])
return best[n]
rob_gap([3, 1, 1, 3]) is 6 and rob_gap([1, 2, 3, 1]) is 3. Time O(n), space O(n) (a rolling window of three values gives O(1)).
A strong answer mentions: best[i] as the best from the first i houses, choosing between skipping house i and robbing it on top of best[i - 3], clamping the index for small i, and that the original problem is the same idea with a gap of two.
1. You need the largest total from a list of numbers where no two chosen numbers may be adjacent, and the list has up to 10^5 entries. Which approach fits best?
The best total after each item depends only on the totals after the previous item, so one pass is O(n). Greedy and sorting can miss better combinations, and trying every subset is exponential.
2. Why does the shown solution need only O(1) extra space?
skip and take are the only values carried forward. The input is not modified, every house is read once, and the code is a loop, not recursion.
3. A learner rewrites the update as two lines, skip = max(skip, take) then take = skip + loot. For which input is the result now wrong?
For [2, 1] the second house sets skip = 2 and then take = 2 + 1, giving 3, which robs two neighbours; the correct answer is 2. For [5], [] and [0, 0] the wrong update happens to give the right answer (5, 0 and 0).
Score 60% or more and the lesson is marked complete.