Coding · Dynamic programming
House Robber
- Reported once
- Medium
- SDE (on-campus, 2021)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A street has houses in a row, each holding some cash, and you may take from any set of houses as long as no two are neighbours. Given the amounts in order, return the most you can take. For example, [2,7,9,3,1] gives 12, by taking from the houses holding 2, 9 and 1. There are up to 100 houses and every amount is zero or more.
Restated in our own words, not a quote from Flipkart or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: can the street be empty, and what do I return then? Can amounts be negative, which would make skipping a house better than taking it? Is the street a straight row or a circle where the first and last houses are neighbours? Do I return only the total or also the chosen houses? How many houses are there?
I will assume a straight row, non-negative integer amounts, an empty street returns 0, and I return the total only. The size is small, but I will write something that would still be fine for a million houses.
Brute force
Say the obvious answer and why it is too slow.
The direct approach is recursion: at each house either take it and jump to the house two steps ahead, or skip it and move to the next one, and keep the larger total. Equivalently, enumerate every set of houses with no two neighbours.
The number of such sets grows like the Fibonacci numbers, roughly 1.6 times larger for every extra house. For 100 houses that is more than 1020 sets, which no computer can enumerate. The waste is clear: the recursion asks "what is the best from house 40 onward" again and again, from different earlier choices. There are only n distinct questions, so we should answer each one once.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(1.6ⁿ)
- Time
- O(n)
- Space
- O(1) extra
Let best(i) be the most I can take from the first i houses. Look at the last house, number i. Either I skip it, which leaves me with best(i - 1), or I take it. If I take it, I cannot take its neighbour, so everything else comes from the first i - 2 houses, which gives amount + best(i - 2). The answer for i is the larger of the two.
Why is this correct? Any optimal plan for the first i houses either includes house i or not. If it does not, the rest of the plan is a valid plan for the first i - 1 houses, and it must be optimal there, or swapping in a better one would improve the whole plan. If it does include house i, the rest is a valid plan for the first i - 2 houses, and again any better plan there could be swapped in. This is optimal substructure.
The recurrence reads only the two previous values, so I do not need an array: two variables, beforePrevious and previous, are enough. That gives O(n) time and O(1) space. The pattern is 1D dynamic programming with a rolling state.
Out loud: "At each house I ask whether taking it beats the best I had one house ago."
Walk it through
A dry run on the example, step by step.
| house | amount | take = two back + amount | skip = previous best | best |
|---|---|---|---|---|
| 0 | 2 | 0 + 2 = 2 | 0 | 2 |
| 1 | 7 | 0 + 7 = 7 | 2 | 7 |
| 2 | 9 | 2 + 9 = 11 | 7 | 11 |
| 3 | 3 | 7 + 3 = 10 | 11 | 11 |
| 4 | 1 | 11 + 1 = 12 | 11 | 12 |
Take [2,7,9,3,1]. Start with both remembered values at 0.
House 0 (2): taking gives 0 + 2 = 2, skipping gives 0, best is 2. House 1 (7): taking gives 0 + 7 = 7, skipping gives 2, best is 7. House 2 (9): taking gives 2 + 9 = 11, skipping gives 7, best is 11. House 3 (3): taking gives 7 + 3 = 10, skipping gives 11, best stays 11. House 4 (1): taking gives 11 + 1 = 12, skipping gives 11, best is 12.
The trace table lists the take and skip values for each house. The final answer is 12.
The code
Runnable JavaScript, checked against test cases.
function rob(nums) {
if (nums.length === 0) return 0;
let beforePrevious = 0;
let previous = 0;
for (let house = 0; house < nums.length; house++) {
const skipHouse = previous;
const robHouse = beforePrevious + nums[house];
beforePrevious = previous;
previous = Math.max(skipHouse, robHouse);
}
return previous;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
An empty street returns 0 through the guard at the top. One house returns that amount, because taking beats the empty skip of 0. Two houses return the larger of the two amounts, since they are neighbours. All zeros return 0.
Equal neighbours such as [5,5] return 5, not 10. A tricky pattern is [2,1,1,2], where the best is 4 by taking the first and last houses, which are not neighbours; any rule that only looks at every other house misses it. Amounts only add, so large streets work as long as the total stays inside a normal number.
Follow-ups to expect
Where the interviewer pushes next.
- How would you solve it if the houses form a circle so the first and last are neighbours?
- How would you recover which houses to take, not only the total?
- What changes if you may not take from houses within two places of each other?
- How does the same recurrence appear in a tree-shaped street?
Where candidates slip
The mistakes this problem punishes.
The popular wrong idea is to add up the odd-position houses and the even-position houses and return the larger. It fails on [2,1,1,2], where both sums are 3 but the answer is 4. A second slip is a greedy "take the biggest house, then remove its neighbours", which fails on [4,5,4], where it takes 5 and ends with 5 instead of 8.
Implementation slips: mixing up which value is two houses back when shifting the two variables (work out the new best from the old pair of values before overwriting either); forgetting that skipping a house must carry forward the previous best, not zero; and crashing on an empty array by reading index 0.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.