House Robber II

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 Approach

The naive approach to solve this problem would be to consider all possible combinations of houses that can be robbed without robbing adjacent houses and then select the combination that yields the maximum amount of money. However, this approach will be extremely inefficient, especially for larger inputs, because the number of combinations grows exponentially.

Optimal Approach

Since the houses are arranged in a circle, the first and last houses are neighbors. This adds a twist to the classic House Robber problem. We can solve this by breaking the 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).

Then, return the maximum of the two.

For each of these subproblems, we can use dynamic programming to find the maximum amount that can be robbed without robbing adjacent houses.

Dynamic Programming

Let dp[i] be the maximum amount that can be robbed from the first i houses. Then, we have the following recurrence relation:

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

where:

• dp[i-1] represents the case where we don't rob the ith house.
• dp[i-2] + nums[i] represents the case where we rob the ith house, so we can't rob the (i-1)th house.

Edge Cases

• If there are no houses or only one house, return 0 or the value of the house, respectively.

Code

def rob(nums):
    def helper(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]

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

    return max(helper(nums[:-1]), helper(nums[1:]))

Complexity Analysis

• Time Complexity: O(n), where n is the number of houses, since we iterate through the houses twice in the helper function.
• Space Complexity: O(n), where n is the number of houses, due to the dp array used in the helper function. This can be optimized to O(1) by using only two variables to store the previous two values of dp.