House Robber II

Problem

You are a professional robber planning to rob houses along a street. All houses at this place are arranged in a circle. Return the maximum amount of money you can rob tonight without alerting the police.

Examples

The brute-force approach

Try all possible subsets of houses. Skip any subset containing two adjacent houses. The first and last house count as adjacent.

best = 0
for mask in range(1 << n):
    valid = True
    for i in range(n):
        if (mask >> i & 1) and (mask >> ((i+1) % n) & 1):
            valid = False
            break
    if valid:
        best = max(best, sum(nums[i] for i in range(n) if mask >> i & 1))
return best

O(2^n × n) — exponential.

Spotting the pattern

This is a Dynamic Programming problem. The key question to ask yourself:

The circular constraint means you can't have both nums[0] and nums[n-1]. What two mutually exclusive scenarios cover all valid solutions?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.