Vinay C.
Data Structures & Algorithms10 min read

House robber

Lesson 7.3 · Medium · Take or skip · 10 min · by Vinay C

We'll cover the following

Each number is the money in a house. You cannot rob two neighbouring houses. Find the most you can take.

Watch it run

Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.

14 items · 15 steps
house120
81
52
53
84
95
156
17
118
119
1010
1011
512
1113

Skip house 0: keep 0. Rob it: 12 + 0 = 12. Best is 12.

best so far [12]

1 / 15

The idea

Complexity

TimeSpaceWhy
O(n)O(1)Only the last two answers are kept.

In Python

def rob(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1
</> Now code it →Try it on LeetCode: House Robber →

Summary: say it in the interview

  • At each house choose: skip it and keep the best so far, or rob it and add the best from two houses back. Take the larger. Every answer depends only on the previous two.
  • Time O(n), space O(1). Only the last two answers are kept.