House Robber

Medium Problem 117 of 151 Java and Python

Practice on LeetCode

Problem

Houses along a street hold nums[i] money each. Robbing two adjacent houses triggers the alarm.

Return the maximum amount you can rob without robbing adjacent houses.

Example 1

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

Example 2

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

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums[i] ≤ 400

Explanation

At house i you either rob it (and add the best up to i - 2) or skip it (and keep the best up to i - 1). So best(i) = max(best(i - 1), best(i - 2) + nums[i]).

Approach 1 · Naive

Recursion: rob or skip

Time O(2ⁿ)
Space O(n)

Try both choices at every house recursively.

rob(i) = best from houses 0..i; negative i gives 0.
rob(i) = max(rob(i - 1), rob(i - 2) + nums[i]).

Java

class Solution {
    public int rob(int[] nums) {
        return best(nums, nums.length - 1);
    }

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

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        def best(i):
            if i < 0:
                return 0
            return max(best(i - 1), best(i - 2) + nums[i])

        return best(len(nums) - 1)

Approach 2 · Optimal

Bottom-up with two variables

Time O(n)
Space O(1)

Scan the houses, keeping the best total up to the previous house and the one before it.

prev2 = prev1 = 0.
For each amount: current = max(prev1, prev2 + amount); shift prev2 = prev1, prev1 = current.
Return prev1.

Java

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

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev2 = prev1 = 0
        for amount in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + amount)
        return prev1

Complexity compared

Approach	Time	Space
Naive Recursion: rob or skip	O(2ⁿ)	O(n)
Optimal Bottom-up with two variables	O(n)	O(1)

Key takeaways

"Take it or leave it, with a constraint on neighbours" is the House Robber pattern; it also appears as Delete and Earn.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem