Problem 24 - House Robber

Explore our archive for previous posts.

Question

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.

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.

Constraints:

• 1 <= nums.length <= 100

• 0 <= nums[i] <= 400

Approach

The solution uses dynamic programming to find the maximum amount that can be robbed without robbing adjacent houses. It iterates through the array, maintaining two variables: prevMax and currMax. At each house, the maximum amount that can be robbed is determined by either robbing the current house along with the amount robbed from the previous non-adjacent house (prevMax + num) or skipping the current house and keeping the maximum amount from the previous house (currMax). By updating these variables iteratively, the solution identifies the maximum amount that can be robbed without adjacent house robberies.

Solution

Solve it here

class Solution {
    public int rob(int[] nums) {

        // Maximum amount that can be robbed from the previous house 
        int prevMax = 0; 
        // Maximum amount that can be robbed from the current house
        int currMax = 0; 
        
        for (int num : nums) {
            // Store the current maximum
            int temp = currMax; 
            
            // Calculate the maximum amount that can be robbed from the current house
            // 2 cases here, and we need max of those
            // a. Rob current house and previous max (excludes last house)
            // b. Skip current house and current max (includes last house)
            currMax = Math.max(prevMax + num, currMax);
            
            // Update the previous maximum to the stored current maximum
            prevMax = temp;
        }
        
        // Return the maximum amount that can be robbed
        return currMax;
    }
}

Time and space complexity

Time Complexity: The time complexity of the solution is O(n), where 'n' is the length of the input array nums. The algorithm iterates through the array once, performing constant-time operations at each step.

Space Complexity: The space complexity is O(1) since the solution uses only a constant amount of additional space. It maintains two variables (prevMax and currMax) to store the maximum amounts, regardless of the input size.

Explore more?

Missed a previous edition? Catch up on the insightful content you might have missed by visiting our archive here. Thank you for being a valued reader of our newsletter. We appreciate your continued support!