House Robber Iv - Leetcode Solution

Problem statement: 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.

Solution: This problem is a follow-up to the House Robber III problem, which can be solved efficiently using dynamic programming. However, the circular arrangement of the houses in this problem complicates the solution.

One possible approach to solve this problem is to divide the circle into two parts: the first part contains houses from the first house to the second-to-last house, and the second part contains houses from the second house to the last house. Then, we can use the solution from the House Robber III problem to find the maximum amount of money we can rob from each part separately, and return the maximum of the two values.

To implement this approach, we can define a helper function that takes an array of money amounts and returns the maximum amount of money we can rob without alerting the police. This helper function can be similar to the solution for the House Robber III problem, where we keep track of the maximum amount of money we can rob up to the i-th house by either skipping it or robbing it, and we update this value for the next house. At the end, we return the maximum amount of money we can rob from all the houses.

Then, in the main function, we can call the helper function twice, once for the first part and once for the second part, and return the maximum of the two values.

Here is the Python code for this approach:

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]
        
        # define a helper function to find the maximum amount of money we can rob from an array of houses
        def rob_houses(nums):
            n = len(nums)
            if n == 1:
                return nums[0]
            if n == 2:
                return max(nums)
            
            # initialize dp array
            dp = [0] * n
            dp[0] = nums[0]
            dp[1] = max(nums[0], nums[1])
            
            # update dp array
            for i in range(2, n):
                dp[i] = max(dp[i-2] + nums[i], dp[i-1])
            
            # return maximum amount of money we can rob
            return dp[-1]
        
        # divide the circle into two parts and find the maximum amount of money we can rob from each part separately
        max1 = rob_houses(nums[:-1])
        max2 = rob_houses(nums[1:])
        
        # return the maximum of the two values
        return max(max1, max2)

Time Complexity: The time complexity of this solution is O(n), where n is the number of houses, because we iterate through all the houses once to find the maximum amount of money we can rob from each part separately, and then we take the maximum of the two values.

Space Complexity: The space complexity of this solution is O(n), where n is the number of houses, because we use a dp array to store the maximum amount of money we can rob up to each house.

1