House Robber

The problem

Houses stand in a row, and nums[i] is the money in house i. You may take the money from any houses you like, except that you can never take from two houses next to each other. Return the most money you can take.

Example 1

Input: nums = [3, 1, 4, 9]

Output: 12

Take houses 0 and 3: 3 + 9 = 12. Taking every other house gives only 3 + 4 = 7 or 1 + 9 = 10.

money

30114293

Example 2

Input: nums = [5]

Output: 5

One house, so take it.

Example 3

Input: nums = [4, 1, 1, 4]

Output: 8

Take the first and the last house. They are not neighbors.

Constraints

• 1 ≤ nums.length ≤ 100 (call it n)
• 0 ≤ nums[i] ≤ 400

Clarifying questions

Can we skip two or more houses in a row?

Yes. The only rule is never two neighbors. Example 1 skips two houses.

Do the first and last house count as neighbors?

No, the street is a straight line. (House Robber II makes it a circle.)

Can a house hold no money?

Yes, 0 is allowed. No amount is negative, so taking a house never lowers the total by itself.

Do we return the houses or the total?

Just the total.

Spot the pattern

Look at the last house. Either we skip it, and the answer is the best for the houses before it. Or we take it, so its neighbor is off limits, and the answer is its money plus the best for the houses two back. Each answer comes from answers to smaller streets, and those repeat. That is dynamic programming.

Solutions

Plain recursionO(2ⁿ)TableO(n)Two numbersO(n)

Show all

Plain recursion O(2ⁿ)

The idea

Let best(house) be the most money from houses 0 to house. For that house there are two choices:

• Skip it: best(house - 1).
• Take it: nums[house] + best(house - 2), since the house just before it must then be skipped.

best(house) is the bigger of the two. When there are no houses, house < 0, the best is 0. The answer is best(len(nums) - 1).

Why it is correct: every allowed choice of houses either includes the last house or does not. The two options cover both cases, and each one is solved for the best possible choice of the rest.

Walkthrough

money

30114293

1. def best(house):
2. # most money from houses 0 .. house
3. if house < 0: return 0
4. return max(best(house - 1), nums[house] + best(house - 2))

best(house) is the most we can take from houses 0 to house. For that house, either skip it, best(house − 1), or take it and skip its neighbor, nums[house] + best(house − 2). The picture is every call best(3) makes.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private int[] nums;

    // Plain recursion: the best haul from houses 0 to i either skips house i
    // or takes it and skips house i - 1. The same smaller cases are solved again and again.
    public int rob(int[] nums) {
        this.nums = nums;
        return best(nums.length - 1);
    }

    private int best(int house) {
        // No houses left: nothing to take.
        if (house < 0) return 0;
        return Math.max(best(house - 1), nums[house] + best(house - 2));
    }
}

Big O

Time O(2ⁿ)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats through recursion, so we count the calls of best. Each call does one check, an addition and a max, a fixed job, so each call counts as 1 step.

   1. def best(house):
   2. # most money from houses 0 .. house
   3. if house < 0: return 0
   4. return max(best(house - 1), nums[house] + best(house - 2))

2. 2 Count the runs on Example 1

   The table counts how often each best(house) was called. The smaller the street, the more often it is asked for: best(0) three times.

   1 + 1 + 2 + 3 + 5 + 3 = 15 calls.

   call	best(3)	best(2)	best(1)	best(0)	best(-1)	best(-2)
   times called	1	1	2	3	5	3

   total

   1 + 1 + 2 + 3 + 5 + 3 = 15 calls

3. 3 Write the count for any n

   Each call makes 2 more calls, and each lowers i by at least 1. Starting from i = n − 1, the calls reach i = −1 or −2, so the tree is at most n + 1 levels deep, and level d holds at most 2ᵈ calls:

   1 + 2 + 4 + … + 2ⁿ = 2ⁿ⁺¹ − 1 calls

   Check it with Example 1: 2⁵ − 1 = 31 at most. The real run made 15, because the take side of the tree is shorter.

4. 4 Keep only the part that grows fastest

   Drop the 2 and the − 1. What is left is 2ⁿ. With 100 houses, that is far too many.

   So the time is O(2ⁿ).

5. S Space: count the extra memory the same way

   The call stack holds one path of the tree at a time, at most n + 1 calls. So the space is O(n).

   call stack (up to n + 1 deep)

Table O(n)

The idea

best(house) only ever needs best(house - 1) and best(house - 2). So fill in the answers from the left, in a table, and each one finds what it needs already there.

To avoid special cases for the first two houses, put two extra 0 slots in front: slot i + 2 holds the answer for houses 0 to i. Then for each house, best[i + 2] = max(best[i + 1], nums[i] + best[i]).

Why it is correct: this is the same rule as the recursion, worked out once per house, in an order where both answers it needs are always filled in.

Walkthrough

money

30114293

best

00

1. best = [0, 0] + [0] * nums_length # slot i + 2 is houses 0 .. i
2. for i in 0 .. nums_length - 1:
3. best[i + 2] = max(best[i + 1], nums[i] + best[i])
4. return best[nums_length + 1]

Fill a table instead. Slot i + 2 holds the best total for houses 0 to i. The first two slots stand for "no houses yet", worth 0, so every house has two slots behind it.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Table, bottom up: best[i + 2] is the most we can take from houses 0 to i.
    // Fill it left to right, so both smaller answers are ready. O(n) time and space.
    public int rob(int[] nums) {
        int numsLength = nums.length;
        // Two extra slots in front stand for "no houses", worth 0.
        int[] best = new int[numsLength + 2];
        for (int i = 0; i < numsLength; i++) {
            // Skip house i, or take it on top of the best from two houses back.
            best[i + 2] = Math.max(best[i + 1], nums[i] + best[i]);
        }
        return best[numsLength + 1];
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The loop body does one addition, one max and one write. That is a fixed job, so each run of the loop counts as 1 step.

   1. best = [0, 0] + [0] * nums_length # slot i + 2 is houses 0 .. i
   2. for i in 0 .. nums_length - 1:
   3. best[i + 2] = max(best[i + 1], nums[i] + best[i])
   4. return best[nums_length + 1]

2. 2 Count the runs on Example 1

   The loop runs once per house.

   4 runs.

   house	0	1	2	3
   loop runs	1	1	1	1

   total

   4 runs

3. 3 Write the count for any n

   The loop goes over every house once:

   n runs

   Check it with Example 1: n = 4 runs. That matches the count.

4. 4 Keep only the part that grows fastest

   Nothing to drop. It is O(n).

   So the time is O(n).

5. S Space: count the extra memory the same way

   The table has n + 2 slots. So the space is O(n).

   best table (n + 2)

Two numbers O(n)

The idea

The table is read only two slots back. So keep just those two answers:

• two_back: the best total up to two houses ago.
• one_back: the best total up to the last house.

For each house, the new best is max(one_back, money + two_back). Then slide: two_back takes the old one_back, and one_back takes the new best.

Why it is correct: the two numbers hold exactly the two table slots the rule needs, so it computes the same answers as the table.

Walkthrough

money

30114293

two_back

0

one_back

0

1. two_back, one_back = 0, 0
2. for money in nums:
3. take = money + two_back
4. two_back, one_back = one_back, max(one_back, take)
5. return one_back

The table only ever reads the two slots behind the one being filled. So keep just two numbers: two_back and one_back, both 0 before any house.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Two numbers: each answer needs only the two before it, so keep just those
    // while walking left to right. O(n) time, O(1) space.
    public int rob(int[] nums) {
        // Best so far up to two houses back, and up to the last house.
        int twoBack = 0, oneBack = 0;
        for (int money : nums) {
            // Skip this house, or take it on top of the best from two houses back.
            int next = Math.max(oneBack, money + twoBack);
            twoBack = oneBack;
            oneBack = next;
        }
        return oneBack;
    }
}

Big O

Time O(n)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The loop body does one addition, one max and two moves. That is a fixed job, so each run of the loop counts as 1 step.

   1. two_back, one_back = 0, 0
   2. for money in nums:
   3. take = money + two_back
   4. two_back, one_back = one_back, max(one_back, take)
   5. return one_back

2. 2 Count the runs on Example 1

   The loop runs once per house.

   4 runs.

   house	0	1	2	3
   loop runs	1	1	1	1

   total

   4 runs

3. 3 Write the count for any n

   n runs

   Check it with Example 1: n = 4. That matches the count.

4. 4 Keep only the part that grows fastest

   Nothing to drop. It is O(n).

   So the time is O(n).

5. S Space: count the extra memory the same way

   Only two_back and one_back are kept, whatever n is. So the space is O(1).

   two_backone_back

Common mistake

Taking every other house

Adding up the even houses or the odd houses, and taking the bigger sum, feels right but is not. Example 1 gives 7 and 10 that way, but the answer is 12: sometimes the best plan skips two houses in a row.

Tested at the limits

2,000 random streets of 1 to 14 houses with amounts 0 to 5, so ties between taking and skipping a house are common. The plain recursion, the table and the two numbers gave the same answer every time.

Largest inputs	Result
100 houses (the most allowed), each with up to 400. Two numbers.	Under 0.001 s, and under 0.001 MB of extra memory: just the two numbers.
25 houses. Plain recursion.	0.02 s. Each extra house makes about 1.6 times more calls, so 100 houses is far out of reach.