House Robber

Medium#1981d array

Houses stand in a row, each with some money in it. Take as much as you can, but never from two houses side by side: that sets off the alarm. Our example: [6, 2, 1, 7, 4, 3] — at most 16, from 6, 7 and 3.

198 House RobberWalkthrough · 1×

Example: [6, 2, 1, 7, 4, 3]. Watch house 4: it has money, and still it is better left alone.

housesbest061221374453
this stepfilledread from, robbednot robbed, not chosenanswer

A table of 7 cells: best[i] is the most money from the first i houses

01/24
restart · back · play · step
Speed
1function rob(houses):
2 best = new array of size len(houses) + 1
3 best[0] = 0 // no houses yet
4 best[1] = houses[0]
5 for i from 2 to len(houses):
6 skip = best[i - 1] // leave house i - 1
7 take = best[i - 2] + houses[i - 1]
8 best[i] = max(skip, take)
9 return best[len(houses)]
state
best
[–, –, –, –, –, –, –]
i
–
skip
–
take
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Look at the last house of the first i: either it is left alone, and the best is the one for the first i − 1, or it is robbed, and its neighbour is not, so the best of the first i − 2 plus its money. Nothing else is possible.
  2. Robbing a house is not always worth it: house 4 brings 4, but taking it rules out the 7 beside it, and 6 + 1 + 4 = 11 loses to 6 + 7 = 13 without it.
  3. Brute force tries every set of houses, about 2ⁿ of them. The table keeps one best per prefix, and each is built from two earlier cells.

Complexity

Time O(n): one cell per house, each from two earlier cells. Memory O(n) for the table; only the last two cells are ever read, so two variables bring it down to O(1).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.