Run it
Three implementations checked against each other, including the empty list.
Why greedy fails, on the case that shows it.
The tuple assignment that is load-bearing, and the circular variant.
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 — and 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.
What to say 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.
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'.
The follow-ups interviewers ask
"The houses are in a circle." The first and last are adjacent, so run the linear version twice - once without the first house, once without the last - and take the better. Every valid selection excludes an end, so one run contains the optimum. A single house needs its own guard.
"Houses arranged in a tree." Same take-or-skip decision, computed bottom-up: for each node return the best with it robbed and the best without, and combine at the parent. It is the natural escalation and it is where the two-value return pays off.
"No two houses within k of each other." best(i-k-1) + house[i], and the rolling window grows from two variables to k+1. The recurrence is the same shape with a longer reach.
Common wrong answers
"Take every other house." Wrong on [2,1,1,2]: alternating gives 3 where taking the two 2s gives 4.
"Always take the largest remaining house." Greedy with no lookahead, and it fails for the same reason it fails in coin change.
"skip = max(skip, take); take = skip + h." Sequential instead of simultaneous, so take reads the new skip and adds the house to a value that already includes its neighbour. The editor prints 22 against the correct 12.
Recap in one screen
- 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.
- Worth trying: 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.
- Worth trying: 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.