Domain 2MediumCORE

House Robber II

We are given an array nums representing money in houses arranged in a circle. The critical constraint is that the first and last houses are neighbors, meaning we cannot rob both house 0 and house n-1 simultaneously if they trigger alarms (which happens for any two adjacent indices). We also cannot rob any other pair of adjacent houses.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Dynamic Programming

213. House Robber II

Model: qwen3.5:9b
Topics: Dynamic Programming
FAANG asked: 0
Acceptance rate: 37.7%


Problem Breakdown

We are given an array nums representing money in houses arranged in a circle. The critical constraint is that the first and last houses are neighbors, meaning we cannot rob both house 0 and house n-1 simultaneously if they trigger alarms (which happens for any two adjacent indices). We also cannot rob any other pair of adjacent houses.

Inputs: An integer array nums where each element represents money in a specific house. Outputs: A single integer representing the maximum amount robbed without triggering an alarm. Constraints & Edge Cases:

  • Array length is between 1 and 100 (non-empty).
  • Values are non-negative integers up to 1000.
  • Critical Logic Constraint: The circular dependency means we cannot treat this as a simple linear array problem directly; the first element restricts the last, and vice versa.

Intuition

This is an extension of the classic “House Robber I” (linear street) problem using Dynamic Programming. In House Robber I, for any house i, we decide whether to rob it or skip it based on the maximum profit from previous non-adjacent houses (dp[i] = max(dp[i-1], dp[i-2] + nums[i])).

The circular constraint introduces a dependency between index 0 and index n-1. If we include house n-1 in our solution, we implicitly exclude house 0. Conversely, if we rob house 0, we must exclude house n-1.

These two scenarios are mutually exclusive but cover all valid configurations:

  1. Scenario A: We do not rob the last house (index n-1). This allows us to treat houses 0 through n-2 as a linear street.
  2. Scenario B: We do not rob the first house (index 0). This allows us to treat houses 1 through n-1 as a linear street.

By solving these two independent House Robber I problems and taking the maximum result, we guarantee that no valid circular configuration is missed without violating adjacency rules.

Approach

I will implement a helper function rob_linear (or similar) that solves the standard non-circular problem using an optimized space approach O(1). In the main solution:

  1. Handle edge case where there is only one house; return its value immediately since no neighbors exist to conflict with in this specific context, though strictly speaking it’s just nums[0].
  2. If length > 1, calculate max profit for range [0 : n-1] (excluding last).
  3. Calculate max profit for range [1 : n] (excluding first).
  4. Return the maximum of these two results.

I will use a space-optimized DP approach within the helper function to avoid allocating an O(N) array, maintaining only prev_max and curr_max.

Complexity Analysis

Time: O(n)O(n) where n is the number of houses. We iterate through the list twice (once for each scenario). Each iteration performs constant work per element. Space: O(1)O(1) auxiliary space if we use variables to store previous DP states, or O(n)O(n) if using an array. I will implement O(1) space in the solution code as it is more efficient and demonstrates optimization awareness.

Solution

def robHouseRobberII(nums):
    """
    Solves House Robber II (Circular Street).
    
    Args:
        nums (List[int]): Money stashed in each house arranged circularly.
        
    Returns:
        int: Maximum amount robbed without alerting police.
    """

    def rob_linear(houses):
        # Standard DP for linear street with O(1) space optimization
        prev = 0
        curr = 0
        
        for money in houses:
            # At each house, decide to take it (curr + money) 
            # or skip it and keep previous max.
            new_curr = max(curr, prev + money)
            prev = curr
            curr = new_curr
            
        return curr

    n = len(nums)
    
    if n == 0:
        return 0
    
    if n == 1:
        # Only one house exists; no adjacency conflict possible.
        return nums[0]
        
    # Case 1: Exclude the last house (indices 0 to n-2)
    max_rob_no_last = rob_linear(nums[:-1])
    
    # Case 2: Exclude the first house (indices 1 to n-1)
    max_rob_no_first = rob_linear(nums[1:])
    
    return max(max_rob_no_last, max_rob_no_first)

# Example usage for verification
if __name__ == "__main__":
    print(robHouseRobberII([2,3,2]))      # Output: 3
    print(robHouseRobberII([1,2,3,1]))   # Output: 4
    print(robHouseRobberII([0]))         # Output: 0

Edge Cases Handled

  • Single House ([x]): The code explicitly checks n == 1. If only one house exists, the circular constraint (first/last neighbor) is trivially satisfied by robbing it. Slicing logic would otherwise produce empty lists which might confuse a naive DP loop; explicit handling prevents this.
  • Two Houses ([a,b]): The code slices nums[:-1] -> [a] and nums[1:] -> [b]. It correctly returns max(a, b), acknowledging that robbing both is impossible as they are neighbors in a circle of 2.
  • Empty Input: Although constraints state length >= 1, the code includes an explicit check for n == 0 returning 0 to ensure robustness against unexpected inputs.