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

  1. Base Cases: If the input array is empty, return 0. If the array has only one house, return the amount of money in that house.

  2. Dynamic Programming: We use dynamic programming to solve this problem. We create a DP array dp of the same size as the input array nums. dp[i] represents the maximum amount of money that can be robbed up to house i (inclusive).

  3. Iteration: We iterate through the nums array. For each house i:

    • If i is 0, dp[i] is simply the amount of money in house 0.
    • If i is 1, dp[i] is the maximum of the amount of money in house 0 or house 1.
    • For i > 1, dp[i] is the maximum of:
      • Robbing house i and adding the maximum amount robbed up to house i-2 (dp[i-2] + nums[i]).
      • Not robbing house i and taking the maximum amount robbed up to house i-1 (dp[i-1]).

  4. Return Value: The maximum amount of money that can be robbed is the last element of the dp array, dp[nums.length - 1].

Explanation

The dynamic programming approach cleverly avoids adjacent house robberies. By considering the maximum robbery amount up to the previous house (dp[i-1]) and the maximum robbery amount up to two houses before (dp[i-2] + nums[i]), we ensure that we never rob adjacent houses. The choice between these two options at each house guarantees that we find the optimal solution.

Code

function rob(nums: number[]): number {
    const n = nums.length;
    if (n === 0) return 0;
    if (n === 1) return nums[0];

    const dp: number[] = new Array(n);
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);

    for (let 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 nums array once.
  • Space Complexity: O(n), where n is the number of houses. We use a DP array of size n. This could be optimized to O(1) by only keeping track of the last two DP values.