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.

For example:

• nums = [2,3,2] should return 3
• nums = [1,2,3,1] should return 4
• nums = [1,2,3] should return 3

## Problem Description

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***.


## Naive Solution (Brute Force)

The most straightforward approach would be to consider all possible combinations of houses that can be robbed without robbing adjacent houses and return the maximum amount among them. However, this approach would have exponential time complexity and is not feasible for larger input sizes.

## Optimal Solution (Dynamic Programming)

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

1.  Rob houses from `nums[0]` to `nums[n-2]` (excluding the last house).
2.  Rob houses from `nums[1]` to `nums[n-1]` (excluding the first house).

We then take the maximum of the results of these two subproblems. For each subproblem, we can use dynamic programming to find the maximum amount that can be robbed.

Here's the code in Python:

```python
def rob_linear(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

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

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

    return dp[n-1]


def rob_circular(nums):
    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]

    # Rob houses from nums[0] to nums[n-2]
    max_rob1 = rob_linear(nums[:-1])

    # Rob houses from nums[1] to nums[n-1]
    max_rob2 = rob_linear(nums[1:])

    return max(max_rob1, max_rob2)

# Example usage:
nums1 = [2,3,2]
print(f"Maximum amount robbed for {nums1}: {rob_circular(nums1)}")

nums2 = [1,2,3,1]
print(f"Maximum amount robbed for {nums2}: {rob_circular(nums2)}")

nums3 = [1,2,3]
print(f"Maximum amount robbed for {nums3}: {rob_circular(nums3)}")

Big(O) Run-time Analysis

The rob_linear function iterates through the input array once, so its time complexity is O(n). The rob_circular function calls rob_linear twice, each time with an array of size approximately n. Therefore, the overall time complexity of the solution is O(n).

Big(O) Space Usage Analysis

The rob_linear function uses a DP array of size n to store intermediate results, thus the space complexity is O(n). The rob_circular function calls rob_linear twice but the DP array is freed after each call, so the overall space complexity is still O(n).

Edge Cases

1. Empty Input: If the input array is empty, the function should return 0, as there is no money to rob.
2. Single House: If there is only one house, the function should return the amount in that house.
3. Two Houses: If there are only two houses, the function should return the maximum of the two amounts.
4. All houses have zero money: The algorithm should correctly return 0 in such cases.
5. Large input array: The DP approach helps to handle larger arrays efficiently without causing stack overflow.