Solution Explanation for House Robber II

This problem extends the classic "House Robber" problem by arranging the houses in a circle. This means the first and last houses are adjacent, and we cannot rob both. We can solve this by breaking it down into two subproblems:

1. Robbing houses from index 0 to n-2 (excluding the last house): This is a standard House Robber problem.
2. Robbing houses from index 1 to n-1 (excluding the first house): This is also a standard House Robber problem.

The maximum amount of money we can rob is the maximum of the results from these two subproblems.

Approach: Dynamic Programming

The core idea is to use dynamic programming to efficiently solve the standard House Robber problem for each subproblem. We can use two variables to track the maximum amount of money we can rob up to a given point.

• f: Represents the maximum money robbed excluding the current house.
• g: Represents the maximum money robbed including the current house.

For each house, we update f and g as follows:

• f becomes the maximum of the previous f and g (we either include or exclude the previous house).
• g becomes the previous f plus the current house's value (we include the current house).

After iterating through all houses, the maximum amount we can rob is max(f, g).

Time and Space Complexity Analysis

• Time Complexity: O(n), where n is the number of houses. We iterate through the array of house values twice (once for each subproblem). The dynamic programming step within each iteration is constant time.

• Space Complexity: O(1). We only use a few constant-size variables (f and g) to store the intermediate results. We don't use any auxiliary data structures that scale with the input size.

Code Implementation in Different Languages

The code implementations below follow the dynamic programming approach. They first define a helper function _rob or robRange that solves the standard House Robber problem. Then, the main rob function calls this helper function twice, once for each subproblem, and returns the maximum of the two results.

Python:

class Solution:
    def rob(self, nums: List[int]) -> int:
        def _rob(nums):
            f = g = 0
            for x in nums:
                f, g = max(f, g), f + x
            return max(f, g)
 
        if len(nums) == 1:
            return nums[0]
        return max(_rob(nums[1:]), _rob(nums[:-1]))

Java:

class Solution {
    public int rob(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        return Math.max(robRange(nums, 0, n - 2), robRange(nums, 1, n - 1));
    }
 
    private int robRange(int[] nums, int l, int r) {
        int f = 0, g = 0;
        for (; l <= r; ++l) {
            int ff = Math.max(f, g);
            g = f + nums[l];
            f = ff;
        }
        return Math.max(f, g);
    }
}

C++, Go, TypeScript, and Rust implementations are provided in the original response and follow the same logic, adapting the syntax and data structures to the specific language. The core dynamic programming algorithm remains consistent across all implementations.