algoadvance

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, which means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, so it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Clarifying Questions

1. Input Constraints:
   • What are the constraints on the size of nums?
     • 1 <= nums.length <= 100
   • What are the constraints on the values within nums?
     • 0 <= nums[i] <= 1000
2. Output:
   • We need to return a single integer representing the maximum amount of money that can be robbed.
3. Special Cases:
   • What if there’s only one house?
     • We simply rob that house since there’s no other house.
   • What if there are two houses?
     • We rob the house with the maximum money since robbing both would alert the police.

Strategy

1. The problem is similar to the “House Robber I” problem, but with the added complexity of houses being in a circle. This means the first and last houses are adjacent.
2. To handle this circular nature, we can simplify the problem by breaking it into two linear “House Robber I” problems:
   • Rob houses from the first to the second-last.
   • Rob houses from the second to the last.
3. The maximum of the above two scenarios will be our result.

Code

Here’s the implementation in Python:

def rob(nums):
    def rob_linear(houses):
        n = len(houses)
        if n == 0:
            return 0
        if n == 1:
            return houses[0]
        if n == 2:
            return max(houses)
        dp = [0] * n
        dp[0] = houses[0]
        dp[1] = max(houses[0], houses[1])
        for i in range(2, n):
            dp[i] = max(dp[i-1], dp[i-2] + houses[i])
        return dp[-1]

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

# Example usage
print(rob([2, 3, 2]))    # Output: 3
print(rob([1, 2, 3, 1])) # Output: 4

Time Complexity

• Let’s denote the length of the list as n.
• Our approach essentially runs the House Robber I dynamic programming solution twice, each on a sub-list of at most length n-1.
• Hence, the time complexity is O(n), as we are performing a linear pass through the input twice.
• The space complexity is also O(n) due to the use of the DP array in the rob_linear function.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?