vizlearn

House robber: the 0-1 choice

Interview QuestionsBy Updated

At each house there are exactly two options: skip it and keep the best from the previous house, or take it and add it to the best from two houses back. best(i) = max(best(i-1), best(i-2) + house[i]) — and since nothing reaches further back than two, two variables replace the whole table.

Dynamic programmingCoding problemMedium

Step through it

What to watch

  • Two options per house, and the recurrence is just the better of them.
  • Taking a house means the answer comes from two back, not one.
  • Nothing reads further back than two, which is why the table can go.

Say this out loud

"At each house I either skip it, keeping best(i-1), or take it and add house[i] to best(i-2), because the neighbour is then off limits. So best(i) is the max of those two. That is O(n) time, and because the recurrence only looks two back I keep two variables instead of an array, so O(1) space. If the houses are in a circle, the first and last are adjacent, so I run it twice - once excluding the first house, once excluding the last - and take the better."

Overview

When adjacent houses cannot both be chosen, the best answer for each prefix is the better of skipping the current house or taking it plus the best non-adjacent prefix. This is a compact dynamic-programming recurrence.

Run it

Three implementations checked against each other, including the empty list.

1Python
Output
Why greedy fails, on the case that shows it.
2Python
Output
The tuple assignment that is load-bearing, and the circular variant.
3Python
Output
The circular variant handles the wraparound by running the linear solution twice, once excluding each end house.
4Python
Output

                

                

                    
Partition by the last decision

                    
The same move as every other question in this group: look at the final choice. Either the last house was robbed or it was not.
If it was not, the answer is whatever was best for the houses before it — best(i-1). If it was, its neighbour cannot have been, so the answer is its value plus the best for everything up to two houses back — best(i-2) + house[i]. Those two cases are exhaustive and disjoint, so the answer is the larger.
The base cases are worth stating explicitly, because off-by-ones here are common: best(0) = 0 (no houses) and best(1) = house[0]. Indexing the table from 1 while the list is indexed from 0 is where the confusion comes from, and the rolling version below makes it disappear.

                

                

                    
Why greedy fails, and what to check

                    
"Take every other house" is the intuition, and it is wrong: [2, 1, 1, 2] gives 3 taking the odd positions, where taking the two 2s gives 4. "Always take the biggest remaining" is also wrong, for the same reason it fails in coin change — no lookahead.
The editor checks the DP against brute force over every valid subset on several inputs, including the empty list and a single house. That is worth doing rather than asserting, because the recurrence is short enough to look obviously right while being wrong at the edges.

                

                

                    
The rolling version, and why it is the one to write

                    
skip = take = 0
for h in houses:
    skip, take = max(skip, take), skip + h
return max(skip, take)
Two names, one pass, no indices. skip is the best with the current house not taken, take the best with it taken — and the simultaneous assignment is what makes it correct: take uses the old skip, which is exactly the two-houses-back value.
Writing it in two steps instead, without the tuple assignment, is the bug: updating skip first means take adds the current house to a value that already includes its neighbour. It is the same hazard as swapping without a temporary.

                

                

                    
The circular variant

                    
"Now the houses are in a circle." The first and last are adjacent, so they cannot both be robbed. The neat resolution is to run the linear solution twice: once on houses[1:] and once on houses[:-1], then take the better. Every valid selection excludes at least one of the two ends, so one of the runs contains the optimum.
The single-house case needs a guard, because both slices are empty and the answer should be that house. That edge is the whole difficulty of the variant, and volunteering it is what an interviewer is listening for.

                

                

                    
Edge cases to raise

                    
Volunteering these is most of what separates a correct answer from a good one.
Empty list. Zero, and a table version indexing best[1] raises before the loop starts.
One house. Take it. The circular variant needs this as a special case, because both of its slices are empty.
Negative values. The recurrence still works, because skipping is always permitted - worth checking rather than assuming, and worth asking about if the problem says 'money'.

                

                

                    
Sources and next steps

                    
                

            


        

    



How the code works
The table, the two-variable version and brute force over every valid subset, checked against each other - then the circular variant and the edge it needs.
How the code works
  1. if mask & (mask >> 1)Two adjacent bits set means two adjacent houses chosen. It is the whole validity test, and it makes brute force short enough to be trustworthy as ground truth.
  2. best[i] = max(best[i - 1], best[i - 2] + houses[i - 1])Skip or take, and nothing else is possible. The i - 1 in the list index against i in the table is the off-by-one the rolling version removes.
  3. skip, take = max(skip, take), skip + hSimultaneous, so take reads the old skip — the two-houses-back value. This is the line to get right.
  4. max(rolling(houses[1:]), rolling(houses[:-1]))Every valid circular selection must exclude at least one end, so running the linear version on each slice covers all of them.
Change one thing
  • Add a negative house value and decide what should happen. The recurrence still works because skipping is always allowed, which is worth checking rather than assuming.
  • Change the rule to "no two houses within k of each other". The recurrence becomes best(i-k-1) + house[i], and the rolling window grows from two variables to k+1.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. What is the recurrence?
  2. Why does taking a house use best(i-2) rather than best(i-1)?
  3. Why can the table be replaced by two variables?
  4. For houses in a circle, the standard solution is:




        
    



 Cheat sheet
House robber: the 0-1 choice
Pick houses to rob without choosing two in a row. Build the DP recurrence, compare rob-or-skip at every step, and read off the maximum take.
INTERVIEW · vizlearn.in/interview/house-robber.html
More in Interview
InterviewWhat does `yield` actually do?InterviewWhy does this default argument remember?Interview`is` vs `==`, and why 257 is not 257InterviewShallow copy vs deep copy
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact