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 nums 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

This problem is a variation of the classic "House Robber" problem. The key difference is that the houses are arranged in a circle. This means robbing the first house prevents robbing the last house, and vice-versa. We can solve this by considering two scenarios:

1. Rob the first house: In this case, we cannot rob the last house. We'll solve the "House Robber" problem for the subarray nums[0...n-2].
2. Don't rob the first house: In this case, we can rob the last house. We'll solve the "House Robber" problem for the subarray nums[1...n-1].

The maximum amount we can rob will be the maximum of these two scenarios.

Explanation

The core logic for solving the "House Robber" subproblem (without the circular constraint) uses dynamic programming. 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 the current house (dp[i-2] + nums[i]).

For the circular case, we apply this logic twice, once for each scenario described above.

Code

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

        // Scenario 1: Rob the first house, skip the last
        int[] dp1 = new int[n - 1];
        dp1[0] = nums[0];
        if (n > 2) dp1[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; i++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }
        int max1 = dp1[n - 2];

        // Scenario 2: Skip the first house, rob the last
        int[] dp2 = new int[n - 1];
        dp2[0] = nums[1];
        if (n > 2) dp2[1] = Math.max(nums[1], nums[2]);
        for (int i = 2; i < n - 1; i++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i + 1]);
        }
        int max2 = dp2[n - 2];


        return Math.max(max1, max2);
    }
}

Complexity

• Time Complexity: O(n), where n is the number of houses. We iterate through the nums array a constant number of times (twice).
• Space Complexity: O(n), due to the dp arrays. This could be optimized to O(1) by using only a few variables to track the maximum values instead of the entire arrays. However, the provided code is clearer for understanding the dynamic programming approach.