House Robber II

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 an integer array nums representing the amount of money of each house, return 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.

Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

# House Robber II

This problem is a variation of the classic House Robber problem, with the added constraint that the houses are arranged in a circle. This means the first and last houses are neighbors, adding a layer of complexity to the problem. We need to find the maximum amount of money we can rob without robbing adjacent houses.

## Naive (Brute Force) Solution

A brute force solution would involve trying all possible combinations of robbing houses while ensuring no adjacent houses are robbed. This approach is highly inefficient, especially with larger arrays.

## Optimal Solution

Since the houses are arranged in a circle, we can break the problem into two subproblems:

1.  Rob houses from index 0 to n-2 (excluding the last house).
2.  Rob houses from index 1 to n-1 (excluding the first house).

We can use the dynamic programming approach used in the classic House Robber problem for each subproblem. The maximum of the two results will be the answer.

### Code

```python
def rob_linear(nums):
    if not nums:
        return 0
    if len(nums) <= 2:
        return max(nums)

    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])

    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])

    return dp[-1]


def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]

    # Rob first house, exclude last
    result1 = rob_linear(nums[:-1])

    # Don't rob first house, include last
    result2 = rob_linear(nums[1:])

    return max(result1, result2)

# Example usage:
nums1 = [2, 3, 2]
print(rob(nums1))  # Output: 3

nums2 = [1, 2, 3, 1]
print(rob(nums2))  # Output: 4

nums3 = [1, 2, 3]
print(rob(nums3))  # Output: 3

nums4 = [1]
print(rob(nums4)) # Output 1

nums5 = [1, 2]
print(rob(nums5)) # Output 2

Explanation

1. rob_linear(nums): This function solves the classic House Robber problem for a linear arrangement of houses.
2. rob(nums): This function splits the circular arrangement into two linear arrangements and calls rob_linear on each.

Big(O) Run-time Analysis

The rob_linear function iterates through the input array once. Thus, it has a time complexity of O(n), where n is the number of houses.

The rob function calls rob_linear twice, each on a sub-array of size n. Therefore, the overall time complexity remains O(n).

Big(O) Space Usage Analysis

The rob_linear function uses an array dp of size n to store the maximum robbery amounts at each house. Therefore, the space complexity of rob_linear is O(n).

The rob function calls rob_linear twice but doesn't store both dp arrays simultaneously. Therefore, the overall space complexity remains O(n).

Edge Cases

1. Empty Array: If the input array is empty, the function should return 0, as there are no houses to rob.
2. Single House: If there is only one house, the function should return the amount of money in that house.
3. Two Houses: If there are only two houses, the function should return the maximum of the two amounts, as we can only rob one of them.
4. All Houses Have Zero Money: If all houses have zero money, the function should return 0.
5. Negative Money: The problem statement indicates that the amount of money in each house is non-negative, so we do not need to handle negative money values.