House Robber
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Houses in a row hold money; you cannot rob two neighbouring houses. Maximise the total.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If you rob house h, what must you have done with house h - 1?
- Hint 2You only need the best totals of the last two houses.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Walking down a street deciding which houses to visit, without ever visiting two adjacent ones. At each house you compare two plans: "skip this house, keep the best total I had after the previous house" or "rob this house, add its money to the best total I had two houses ago (the previous house must be skipped)". Keep the better one and walk on.
- The obvious way
Try every set of non-adjacent houses recursively: O(2^n).
- The key insight
Keep best_one_back (best total through the previous house) and best_two_back (through the house before that). For each house: best_now = max(best_one_back, best_two_back + money). Then shift the two variables one house forward.
- The algorithm
- Both bests start at 0.
- For each house: best_now = max(best_one_back, best_two_back + money).
- Shift: two_back = one_back, one_back = best_now.
- Return the last best.
Watch it run
Examplenums = [2, 7, 9, 3, 1]
House 1 (2): rob it. Best so far 2.
best = 2
Where people slip
- Do not simply alternate houses; the best plan can skip two houses in a row.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def rob(nums):
best_two_back, best_one_back = 0, 0 # best totals through the last two houses
for money in nums:
best_now = max(best_one_back, best_two_back + money) # skip this house, or rob it
best_two_back, best_one_back = best_one_back, best_now
return best_one_backNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.