House Robber II

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

A naive approach would involve considering all possible combinations of houses to rob and choosing the one that yields the maximum amount without robbing adjacent houses. However, this would have exponential time complexity, making it impractical for larger inputs.

Optimal Solution

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

1. Rob houses from nums[0] to nums[n-2]. This excludes the last house.
2. Rob houses from nums[1] to nums[n-1]. This excludes the first house.

We can then use dynamic programming to solve each subproblem. For each subproblem, we maintain two variables:

• include: The maximum amount of money we can rob if we include the current house.
• exclude: The maximum amount of money we can rob if we exclude the current house.

For each house, we update these variables as follows:

• include = exclude + nums[i]
• exclude = max(include, exclude)

Finally, we return the maximum of the maximum amounts obtained from the two subproblems.

Edge Cases

• If the array is empty, return 0.
• If the array has only one element, return that element.
• If the array has only two elements, return the maximum of the two elements.

Code

def rob(nums):
    def helper(nums):
        include = 0
        exclude = 0
        for num in nums:
            new_include = exclude + num
            new_exclude = max(include, exclude)
            include = new_include
            exclude = new_exclude
        return max(include, exclude)

    n = len(nums)
    if n == 0:
        return 0
    if n == 1:
        return nums[0]
    return max(helper(nums[:-1]), helper(nums[1:]))

Time and Space Complexity

• Time Complexity: O(n), where n is the number of houses, as we iterate through the array twice.
• Space Complexity: O(1), as we use a constant amount of extra space.