House Robber

Problem

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Examples

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Similar Problems

[House Robber 2 - Houses in circle](house-robber-2-houses-in-circle) [House Robber 3 - Houses in Binary Tree](house-robber-3-houses-in-binary-tree) [House Robber 4](house-robber-4)

Solution

Video explanation

Here is the video explaining below methods in detail. Please check it out:

<div class="youtube-embed"><iframe src="https://www.youtube.com/embed/yN1ukvWjMJY" frameborder="0" allowfullscreen></iframe></div>

Method 1 - Naive

The naive approach computes the largest possible amount of money we can rob by explicitly examining all potential combinations of houses.

The idea is simple:

1. At every house, we have two choices:
   • Either, Rob the house (add the house's money to the total and skip the adjacent house).
   • or Skip it ( and move to the next house).
2. Take the maximum amount of money between these two choices. rob(i) = max(rob(i+1), nums[i] + rob(i+2))
3. Continue evaluating recursively for the rest of the houses.

This is how the recursion tree looks for example 2 [2, 7, 9, 3, 1]:

 graph TD
     rob0["rob(0) (choose 2)"]
     rob0 --> rob0case["2 + rob(2)"]
     rob0 --> skip0["rob(1) (skip 2)"]
     
     rob0case --> rob2case["9 + rob(4)"]
     rob0case --> skip2["rob(3) (skip 9)"]
     
     skip0 --> rob1case["7 + rob(3)"]
     skip0 --> skip1["rob(2) (skip 7)"]
     
     rob2case --> rob4case["1 + rob(5)"]
     rob2case --> skip5["rob(5) (skip 1)"]
     
     skip2 --> rob3case["3 + rob(5)"]
     skip2 --> skip4["rob(4) (skip 3)"]
     
     rob1case --> rob3subcase["3 + rob(5)"]
     rob1case --> skip3["rob(4) (skip 3)"]
     
     skip1 --> rob2alt["9 + rob(4)"]
     skip1 --> skip3alt["rob(3) (skip 9)"]
 
     rob3case --> base1["Base Case: 0"]
     skip4 --> base2["Base Case: 1"]
     rob4case --> base3["Base Case: 0"]
     skip5 --> base4["Base Case: 0"]
     rob2alt --> base5["Base Case: 1"]
     skip3 --> base6["Base Case: 1"]
     rob3subcase --> base7["Base Case: 0"]
     skip3alt --> base8["Base Case: 1"]

Code

Java

class Solution {
    public int rob(int[] nums) {
        return robHouse(nums, 0);
    }
    
    private int robHouse(int[] nums, int index) {
        // Base case: no houses left to rob
        if (index >= nums.length) {
            return 0;
        }
        
        // Option 1: Skip the house
        int skip = robHouse(nums, index + 1);
        
        // Option 2: Rob the house
        int rob = nums[index] + robHouse(nums, index + 2);
        
        // Take the maximum
        return Math.max(skip, rob);
    }
}

Python

class Solution:
    def rob(self, nums: list[int]) -> int:
        def rob_house(index: int) -> int:
            # Base case: no houses left to rob
            if index >= len(nums):
                return 0
            
            # Option 1: Skip the current house
            skip = rob_house(index + 1)
            
            # Option 2: Rob the current house
            rob = nums[index] + rob_house(index + 2)
            
            # Take the maximum
            return max(skip, rob)
        
        return rob_house(0)

Complexity

• ⏰ Time complexity: O(2^n). Each house creates two recursive calls (rob(i+1) and rob(i+2)), leading to exponential growth in the recursion tree.
• 🧺 Space complexity: O(n). The recursion depth in the call stack can reach up to n (the number of houses).

Method 2 - Top-down DP with Memoization

In the naive approach, we have a lot of repeating subproblems, which we can cache the first time we compute them and reuse them later.

Code

Java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        int[] cache = new int[n]; // Create an integer array as the cache
        Arrays.fill(cache, -1); // Initialise the cache with -1
        
        return helper(nums, 0, cache);
    }
    
    private int helper(int[] nums, int index, int[] cache) {
        // Base case: if index is out of bounds, return 0
        if (index >= nums.length) {
            return 0;
        }
        
        // If value is cached, directly return it
        if (cache[index] != -1) {
            return cache[index];
        }
        
        // Recurrence relation: rob the current house or skip it
        int robCurrent = nums[index] + helper(nums, index + 2, cache);
        int skipCurrent = helper(nums, index + 1, cache);
        
        // Store the result in the cache
        cache[index] = Math.max(robCurrent, skipCurrent);
        return cache[index];
    }
}

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        cache = [-1] * n  # Create an integer array as the cache
        
        def helper(index: int) -> int:
            # Base case: if index is out of bounds, return 0
            if index >= n:
                return 0
            
            # If value is cached, directly return it
            if cache[index] != -1:
                return cache[index]
            
            # Recurrence relation: rob the current house or skip it
            rob_current = nums[index] + helper(index + 2)
            skip_current = helper(index + 1)
            
            # Store the result in the cache
            cache[index] = max(rob_current, skip_current)
            return cache[index]
        
        return helper(0)

Complexity

• ⏰ Time complexity: O(n). Each house index is computed only once and stored in the cache.
• 🧺 Space complexity: O(n). The recursion stack can go as deep as n, and the cache stores up to n results.

Method 3 - Bottom-up Dynamic Programming

Here are the steps:

1. Initialise a DP Array: Create an array dp of size n (number of houses).
2. Set the Base Cases:
   • dp[0] = nums[0]
   • If there are at least two houses, dp[1] = max(nums[0], nums[1]).
3. Iteratively Fill the DP Array:
   • Start from the third house (i = 2) and calculate: dp[i] = max(nums[i] + dp[i-2], dp[i-1])
   • Move from the beginning to the end of the array, updating the array step by step.
4. Result:
   • The value in dp[n-1] (the last cell of the DP array) will be the maximum amount of money that can be robbed.

Code

Java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        
        // Initialise the DP array
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        
        // Build the DP array from the start
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
        }
        
        return dp[n-1];
    }
}

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        # Initialise the DP array
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        # Build the DP array from the start
        for i in range(2, n):
            dp[i] = max(nums[i] + dp[i-2], dp[i-1])
        
        return dp[n-1]

Complexity

• ⏰ Time complexity: O(n). Filling the dp array requires iterating through all n houses.
• 🧺 Space complexity: O(n). The dp array uses O(n) space to store intermediate results.

Method 4 - Space-optimized bottom up DP

When we look closely at the recurrence relation:

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

Each result `dp[i]` depends only on the previous two values (`dp[i-1]` and `dp[i-2]`) and **not the entire DP array**.

2. So, instead of maintaining a full dp array, we can optimise space by using two variables: - prev1: Represents dp[i-1] (the maximum loot up to the previous house). - prev2: Represents dp[i-2] (the maximum loot up to two houses behind). - This approach is similar to other problems, like [generating the nth Fibonacci number](generate-nth-fibonacci-number). 3. As we iterate through the houses, these two variables are dynamically updated to compute the result.

Code

Java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        
        // Base Cases
        int prev2 = nums[0]; // Equivalent to dp[0]
        int prev1 = Math.max(nums[0], nums[1]); // Equivalent to dp[1]
        
        // Iterate from index 2 to n-1
        for (int i = 2; i < n; i++) {
            int curr = Math.max(nums[i] + prev2, prev1); // Calculate current house loot
            prev2 = prev1; // Update prev2 to previous prev1
            prev1 = curr;  // Update prev1 to current value
        }
        
        return prev1;
    }
}

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        # Base Cases
        prev2 = nums[0]  # Equivalent to dp[0]
        prev1 = max(nums[0], nums[1])  # Equivalent to dp[1]
        
        # Iterate from index 2 to n-1
        for i in range(2, n):
            curr = max(nums[i] + prev2, prev1)  # Calculate current house loot
            prev2, prev1 = prev1, curr  # Update variables for the next iteration
        
        return prev1

Complexity

• ⏰ Time complexity: O(n), as we iterate through all n houses once.
• 🧺 Space complexity: O(1), as we only use two variables (prev1 and prev2) for intermediate computations.

Method 5 - Bottom-up Dynamic Programming but starting from behind

We can also use bottom up dp approach, by starting from the end of the array. The dp recurrence relation is then similar to recursive top down approach. Here are the steps:

1. Instead of starting from the first house (as in recursion), we solve the problem backwards (from the last house to the first house).
2. We'll use a DP array (dp) where each dp[i] represents the maximum amount of money that can be robbed starting from house i.
3. Base Cases:
   • If there's no house (i >= n), dp[i] = 0.
   • If there's one house at the end (dp[n-1]), dp[n-1] = nums[n-1].
4. The relationship remains the same as in the recursive approach: dp[i] = max(nums[i] + dp[i+2], dp[i+1])

Code

Java

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) return nums[0];
        
        // Initialise the DP array
        int[] dp = new int[n + 1];
        dp[n] = 0;  // No houses left
        dp[n-1] = nums[n-1];  // Only one house
        
        // Fill the DP array from the end
        for (int i = n - 2; i >= 0; i--) {
            dp[i] = Math.max(nums[i] + dp[i+2], dp[i+1]);
        }
        
        return dp[0];
    }
}

Python

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        
        # Initialise the DP array
        dp = [0] * (n + 1)
        dp[n] = 0  # No houses left
        dp[n-1] = nums[n-1]  # Only one house
        
        # Fill the DP array from the end
        for i in range(n-2, -1, -1):
            dp[i] = max(nums[i] + dp[i+2], dp[i+1])
        
        return dp[0]

Complexity

• ⏰ Time complexity: O(n). Filling the dp array takes O(n) time, as we iterate through all houses once.
• 🧺 Space complexity: O(n). The dp array requires O(n + 1) space, which is proportional to the number of houses.