House Robber medium

Problem Statement

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 a list of non-negative integers representing the amount of money of each house, determine 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.

Steps and Explanation

This problem can be solved using dynamic programming. The core idea is that the maximum amount of money you can rob at a given house depends only on the maximum amount you could rob at the previous two houses.

Let dp[i] represent the maximum amount of money you can rob up to house i (including house i). Then:

• dp[0] = nums[0] (If there's only one house, you rob it)
• dp[1] = max(nums[0], nums[1]) (If there are two houses, you rob the one with more money)
• dp[i] = max(dp[i-1], dp[i-2] + nums[i]) for i >= 2. This means you either rob house i (adding its value to the maximum you could rob from houses up to i-2) or you don't rob house i (and take the maximum from houses up to i-1).

We iterate through the nums array, calculating dp[i] at each step. The final result will be dp[n-1], where n is the number of houses.

Code (Java)

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }

        return dp[n - 1];
    }
}

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the array once.
• Space Complexity: O(n), where n is the number of houses. We use a dp array of size n. This can be optimized to O(1) by only storing the previous two maximum values instead of the entire array. (See Optimized Code below)

Optimized Code (Java) - O(1) Space

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        int prev1 = nums[0];
        int prev2 = Math.max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            int current = Math.max(prev2, prev1 + nums[i]);
            prev1 = prev2;
            prev2 = current;
        }

        return prev2;
    }
}

This optimized version achieves the same result with constant space complexity by only tracking the two previous maximum values.