House Robber II

Difficulty: Medium Source: NeetCode

Problem

You are a professional robber planning to rob houses along a street. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. If two adjacent houses are broken into, the police are alerted.

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.

Example 1: Input: nums = [2,3,2] Output: 3

Example 2: Input: nums = [1,2,3,1] Output: 4

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

• House Robber I — linear house robber DP
• Circular Constraint Reduction — breaking a circular problem into two linear subproblems

1. Brute Force (All Subsets)

Intuition

Try every possible subset of houses, skip any subset where two adjacent houses (including first and last) are both selected, and return the maximum sum. Exponential time but correct.

Solution

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

    best = 0
    for mask in range(1 << n):
        total = 0
        valid = True
        for i in range(n):
            if mask & (1 << i):
                # Check adjacency (including wrap-around)
                if mask & (1 << ((i + 1) % n)):
                    valid = False
                    break
                total += nums[i]
        if valid:
            best = max(best, total)
    return best


print(rob_brute([2, 3, 2]))   # 3
print(rob_brute([1, 2, 3, 1]))  # 4
print(rob_brute([1, 2, 3]))   # 3

Complexity

• Time: O(2^n * n) — exponential
• Space: O(1)

2. Two-Pass Linear DP

Intuition

The circular constraint means house 0 and house n-1 are neighbors — you can’t rob both. The key insight: at least one of house 0 or house n-1 is NOT robbed in any optimal solution. So we can break the problem into two independent linear House Robber I problems:

1. Rob houses 0..n-2 (exclude the last house)
2. Rob houses 1..n-1 (exclude the first house)

Take the maximum of both. This guarantees we never rob both the first and last houses simultaneously.

Algorithm

1. If n == 1, return nums[0].
2. Run House Robber I on nums[:-1] (skip last).
3. Run House Robber I on nums[1:] (skip first).
4. Return the max of both results.

Solution

def rob(nums):
    n = len(nums)
    if n == 1:
        return nums[0]
    if n == 2:
        return max(nums)

    def rob_linear(houses):
        if not houses:
            return 0
        if len(houses) == 1:
            return houses[0]
        prev2 = houses[0]
        prev1 = max(houses[0], houses[1])
        for i in range(2, len(houses)):
            curr = max(prev1, prev2 + houses[i])
            prev2 = prev1
            prev1 = curr
        return prev1

    # Option 1: rob houses 0..n-2 (exclude last)
    # Option 2: rob houses 1..n-1 (exclude first)
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))


print(rob([2, 3, 2]))    # 3
print(rob([1, 2, 3, 1]))  # 4
print(rob([1, 2, 3]))    # 3  (rob 1 and 3)
print(rob([1]))           # 1
print(rob([1, 2]))        # 2

Complexity

• Time: O(n) — two linear passes
• Space: O(1) — only rolling variables (if we pass slices it’s O(n), but we can pass indices instead)

Common Pitfalls

Forgetting the n=1 and n=2 edge cases. For one house, rob it. For two houses, take the larger. The main two-pass logic assumes at least three houses.

Thinking you need to try all four combinations. It might seem like you need to check “rob first, skip last”, “skip first, rob last”, “skip both”, and “rob both”. You don’t — “rob both” is illegal, and the other three cases are all covered by the two linear subproblems (skipping one endpoint each time).

Passing slices creates new lists. nums[:-1] and nums[1:] create copies in Python. For large inputs, you could instead pass index ranges to the linear robber to avoid the extra allocation.