House Robber II medium

Problem Statement

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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 = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2

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.

Steps

The key insight is that because the houses are in a circle, robbing the first house prevents robbing the last house, and vice-versa. Therefore, we can solve this problem by considering two cases:

1. Rob the first house: In this case, we cannot rob the last house. We can use a dynamic programming approach to find the maximum amount we can rob from houses 0 to n-2.
2. Don't rob the first house: In this case, we can rob the last house. We use a dynamic programming approach to find the maximum amount we can rob from houses 1 to n-1.

We then return the maximum of these two amounts.

Explanation

The dynamic programming approach used in each case is similar to the standard House Robber problem (without the circular constraint). We create a dp array where dp[i] represents the maximum amount we can rob considering houses up to index i. The recurrence relation is:

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

This means we can either skip the current house (dp[i-1]) or rob it (dp[i-2] + nums[i]), choosing the option that yields the maximum amount.

Code

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

    if (n === 0) return 0;
    if (n === 1) return nums[0];

    // Case 1: Rob the first house, skip the last
    let dp1 = new Array(n - 1).fill(0);
    dp1[0] = nums[0];
    dp1[1] = Math.max(nums[0], nums[1]);
    for (let i = 2; i < n - 1; i++) {
        dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
    }

    // Case 2: Skip the first house, rob the last
    let dp2 = new Array(n - 1).fill(0);
    dp2[0] = nums[1];
    dp2[1] = Math.max(nums[1], nums[2]);
    for (let i = 2; i < n - 1; i++) {
        dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
    }

    return Math.max(dp1[n - 2], dp2[n - 2]);
}

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the nums array twice.
• Space Complexity: O(n) for the dp arrays. This can be optimized to O(1) by using only a few variables to track the previous two maximum amounts instead of the entire arrays. A space-optimized solution would reduce the space complexity, but this solution prioritizes clarity.