71. House Robber · DSA Practice

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

Example 1

Input: nums = [2,7,9,3,1]

Output: 12

Explanation: Rob houses with 2, 9 and 1.

Example 2

Input: nums = [6,7,1,30,8,2,4]

Output: 41

Explanation: Rob 7, 30 and 4.

Hint 1

dp[i] = max(dp[i−1], dp[i−2] + nums[i]): either skip house i or rob it.

Dynamic Programming

Approach 1: Recursion

Try rob/skip at each house.

⏱ Time O(2ⁿ)💾 Space O(n)

Approach 2: DP with two variables ✅

Rolling dp[i−1] and dp[i−2].

⏱ Time O(n)💾 Space O(1)

Reference solution for DP with two variables (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev, curr = 0, 0                 # best up to house i-2, i-1
        for x in nums:
            prev, curr = curr, max(curr, prev + x)   # skip house i, or rob it
        return curr

class Solution {
    public int rob(int[] nums) {
        int prev = 0, curr = 0;           // best up to house i-2, i-1
        for (int x : nums) { int next = Math.max(curr, prev + x); prev = curr; curr = next; }
        return curr;
    }
}

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev = 0, curr = 0;           // best up to house i-2, i-1
        for (int x : nums) { int next = max(curr, prev + x); prev = curr; curr = next; }
        return curr;
    }
};

function rob(nums) {
  let prev = 0, curr = 0; // best up to house i-2, i-1
  for (const x of nums) [prev, curr] = [curr, Math.max(curr, prev + x)];
  return curr;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Dynamic Programming (1-D).