House Robber

Medium Dynamic Programming Alternate Selection / Pick / Not pick Original on LeetCode

House Robber is a medium dynamic programming problem solved with the alternate selection / pick / not pick pattern. The best approach, optimal (two variables), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from recursion (pick / not pick) up.

Problem

Houses along a street hold nums[i] money. You cannot rob two adjacent houses. Return the maximum amount you can rob.

Examples

Example 1

Input
nums = [2, 7, 9, 3, 1]
Output
12
Why
Rob houses 0, 2 and 4: 2 + 9 + 1.

Example 2

Input
nums = [5, 1, 1, 5]
Output
10
Why
Houses 0 and 3. Taking every other house is not always optimal.

Constraints

  • 1 <= nums.length <= 100; 0 <= nums[i] <= 400.
  • Adjacent houses cannot both be robbed.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Recursion (pick / not pick)O(2ⁿ)O(n)
TabulationO(n)O(n)
Optimal (two variables)O(n)O(1)

1Recursion (pick / not pick)

TimeO(2ⁿ)
SpaceO(n)

best(i) = max(best(i - 1), nums[i] + best(i - 2)).

  1. Base: i < 0 → 0.
class Solution {
    public int rob(int[] nums) {
        return best(nums, nums.length - 1);
    }

    private int best(int[] a, int i) {
        if (i < 0) return 0;
        return Math.max(best(a, i - 1), a[i] + best(a, i - 2));
    }
}

2Tabulation

TimeO(n)
SpaceO(n)

dp[i] = best loot from the first i houses.

  1. dp[0] = 0, dp[1] = nums[0].
  2. dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]).
class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[1] = nums[0];
        for (int i = 2; i <= n; i++) dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        return dp[n];
    }
}

3Optimal (two variables)

TimeO(n)
SpaceO(1)

Keep the best up to the previous house and the one before it.

  1. prev2 = 0, prev1 = 0; cur = max(prev1, prev2 + x); shift.
class Solution {
    public int rob(int[] nums) {
        int prev2 = 0, prev1 = 0;
        for (int x : nums) {
            int cur = Math.max(prev1, prev2 + x);
            prev2 = prev1;
            prev1 = cur;
        }
        return prev1;
    }
}

Edge cases to test

  • One or two houses

Hints

Hint 1

At house i, either skip it (keep the best up to i - 1) or rob it (its value plus the best up to i - 2).

FAQ

What is the best time complexity for House Robber?

Optimal (two variables) runs in O(n) time and O(1) extra space.

Which pattern does House Robber use?

It is a dynamic programming problem that uses the alternate selection / pick / not pick pattern. Other problems with the same pattern: House Robber II.

Is there a brute force solution for House Robber?

Yes. Recursion (pick / not pick) takes O(2ⁿ) time and O(n) space. best(i) = max(best(i - 1), nums[i] + best(i - 2)).

Which edge cases should I test for House Robber?

One or two houses.