Problem Description

You need to plan a robbery along a street where houses are arranged in a circle. This means the first house and the last house are neighbors of each other.

Each house contains a certain amount of money, represented by an integer array nums where nums[i] is the amount of money in house i.

The constraint is that houses have a security system - if you rob two adjacent houses on the same night, the police will be alerted automatically.

Your goal is to find the maximum amount of money you can rob without triggering the security system (without robbing any two adjacent houses).

The key difference from a standard house robbing problem is the circular arrangement. Since the houses form a circle:

• If you rob the first house, you cannot rob the last house (they are adjacent)
• If you rob the last house, you cannot rob the first house

Given the array nums, return the maximum total amount you can rob.

For example:

• If nums = [2, 3, 2], you cannot rob house 0 and house 2 together since they are adjacent in the circle. The maximum would be 3 (robbing only house 1).
• If nums = [1, 2, 3, 1], you could rob houses 0 and 2 for a total of 4, or just house 2 for 3, so the maximum is 4.

The solution cleverly handles this by considering two scenarios:

1. Rob houses from index 1 to n-1 (excluding the first house)
2. Rob houses from index 0 to n-2 (excluding the last house)

Then take the maximum of these two scenarios, effectively ensuring the first and last houses are never both robbed.

Intuition

The circular arrangement creates a unique constraint: we cannot rob both the first and last houses since they're neighbors. This observation is the key to solving the problem.

Think about it this way - in a circular arrangement, we have three possible scenarios:

1. We rob the first house but not the last house
2. We rob the last house but not the first house
3. We rob neither the first nor the last house

Notice that scenario 3 is automatically covered by scenarios 1 and 2 (since we're looking for the maximum, if neither first nor last gives us the best result, that case will naturally emerge).

This insight allows us to break down the circular problem into two simpler linear problems:

• Case 1: Consider houses from index 0 to n-2 (exclude the last house)
• Case 2: Consider houses from index 1 to n-1 (exclude the first house)

By solving these two linear subproblems separately and taking the maximum, we ensure that we never rob both the first and last houses together.

For each linear subproblem, we can use dynamic programming. At each house, we have two choices:

• Rob the current house: We get the money from this house plus the maximum money we could have robbed up to the house before the previous one
• Skip the current house: We keep the maximum money we could have robbed up to the previous house

The variables f and g in the solution track these two states:

• f: Maximum money robbed without robbing the current house
• g: Maximum money robbed if we rob the current house

The update rule f, g = max(f, g), f + x elegantly captures this logic, where x is the current house's money.

Solution Approach

The solution uses Dynamic Programming to solve this circular house robbing problem by reducing it to two linear subproblems.

Main Strategy: Since we cannot rob both the first and last houses (they're adjacent in the circle), we solve two separate linear problems:

1. Rob from houses [1, n-1] (excluding first house)
2. Rob from houses [0, n-2] (excluding last house)

Implementation Details:

The helper function _rob(nums) solves the linear house robbing problem using space-optimized dynamic programming:

def _rob(nums):
    f = g = 0
    for x in nums:
        f, g = max(f, g), f + x
    return max(f, g)

Here's how the state variables work:

• f: Maximum money robbed without robbing the current house
• g: Maximum money robbed with robbing the current house
• x: Money in the current house

State Transition:

• New f = max(f, g): The maximum we can get without robbing current house is the better of our previous two states
• New g = f + x: If we rob the current house, we add its value to the maximum we had without robbing the previous house

Edge Case Handling:

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

When there's only one house, we simply rob it since there are no adjacency constraints.

Final Solution:

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

• _rob(nums[1:]): Maximum money when excluding the first house
• _rob(nums[:-1]): Maximum money when excluding the last house
• Return the maximum of these two scenarios

Time Complexity: O(n) - We traverse the array twice Space Complexity: O(1) - Only using constant extra space (the slicing creates new arrays but the DP itself uses constant space)

Example Walkthrough

Let's walk through the solution with nums = [2, 7, 9, 3, 1].

Since houses form a circle, house 0 (value=2) and house 4 (value=1) are neighbors. We need to find the maximum money without robbing adjacent houses.

Step 1: Break into two linear problems

• Case 1: Exclude first house → Consider [7, 9, 3, 1] (indices 1-4)
• Case 2: Exclude last house → Consider [2, 7, 9, 3] (indices 0-3)

Step 2: Solve Case 1 - [7, 9, 3, 1]

Using the _rob function with f (skip current) and g (rob current):

Result: max(10, 10) = 10 (rob houses at indices 1 and 3 → values 7 and 3)

Step 3: Solve Case 2 - [2, 7, 9, 3]

Result: max(11, 10) = 11 (rob houses at indices 0 and 2 → values 2 and 9)

Step 4: Final answer Return max(10, 11) = 11

The optimal solution is to rob houses at indices 0 and 2 (values 2 and 9) for a total of 11, which avoids robbing adjacent houses in the circle.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The algorithm calls the helper function _rob twice - once with nums[1:] and once with nums[:-1]. Each call to _rob iterates through approximately n-1 elements, performing constant time operations (max and addition) for each element. Therefore, the total time complexity is O(n-1) + O(n-1) = O(n).

The space complexity is O(n). While the helper function _rob uses only O(1) space with variables f and g, the slicing operations nums[1:] and nums[:-1] each create new arrays of size n-1, requiring O(n) additional space. The reference answer states O(1) space complexity, which would be achievable if the code used index-based iteration instead of array slicing.

Common Pitfalls

1. Not Handling Edge Cases Properly

A frequent mistake is forgetting to handle special cases, particularly when the array has only 1 or 2 elements. The circular constraint doesn't apply meaningfully to these cases.

Incorrect approach:

def rob(self, nums: List[int]) -> int:
    # Directly applying the two-scenario logic without edge case handling
    return max(self._rob(nums[1:]), self._rob(nums[:-1]))
    # This fails when nums has only 1 element because nums[1:] would be empty

Correct approach:

def rob(self, nums: List[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    if len(nums) == 2:
        return max(nums[0], nums[1])
    return max(self._rob(nums[1:]), self._rob(nums[:-1]))

2. Confusing State Variables in Dynamic Programming

Many people mix up what each DP variable represents, leading to incorrect state transitions.

Incorrect approach:

def _rob(nums):
    f = g = 0
    for x in nums:
        # Wrong: Using g in both transitions
        f, g = g, g + x  # This doesn't maintain the "skip previous house" constraint
    return max(f, g)

Correct approach:

def _rob(nums):
    f = g = 0  # f: max without robbing current, g: max with robbing current
    for x in nums:
        # f becomes max of previous states, g uses old f (skip previous) + current
        f, g = max(f, g), f + x
    return max(f, g)

3. Creating Unnecessary Space Complexity

Using a full DP array when only the last two states are needed.

Space-inefficient approach:

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

Space-efficient approach:

def _rob(nums):
    prev2 = prev1 = 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

4. Misunderstanding the Circular Constraint

Some attempt to handle the circular nature within the DP logic itself, making the solution unnecessarily complex.

Overly complex approach:

def rob(self, nums: List[int]) -> int:
    # Trying to track whether first house was robbed throughout the DP
    # This leads to complicated state management and is error-prone
    dp = [[0, 0] for _ in range(len(nums))]  # [robbed_first, not_robbed_first]
    # Complex logic follows...

Simple and correct approach:

def rob(self, nums: List[int]) -> int:
    # Simply solve two separate linear problems
    if len(nums) == 1:
        return nums[0]
    return max(rob_linear(nums[1:]), rob_linear(nums[:-1]))

5. Array Slicing Performance Concerns

While nums[1:] and nums[:-1] are clean, they create new arrays. In performance-critical scenarios, using indices might be better.

More memory-efficient approach:

def rob(self, nums: List[int]) -> int:
    def rob_range(start, end):
        f = g = 0
        for i in range(start, end):
            f, g = max(f, g), f + nums[i]
        return max(f, g)
  
    if len(nums) == 1:
        return nums[0]
    return max(rob_range(1, len(nums)), rob_range(0, len(nums)-1))