Skip to content

132 — House Robber II

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

132 — House Robber II

LeetCode 213 · Medium. All houses are arranged in a circle — the first house and the last house are adjacent neighbors. Given an integer array nums representing the amount of money at each house, return the maximum amount of money you can rob tonight without robbing two adjacent houses (including the first-and-last wraparound pair).

🍽️ Intuition

The only new wrinkle over House Robber is that the street bends into a loop, so house 0 and the last house are now neighbors too. That one extra adjacency ruins the clean left-to-right sweep — until you notice that any valid robbery plan either leaves house 0 alone, or leaves the last house alone (it can never rob both, since they're adjacent). So instead of solving one circular problem, solve two ordinary linear House Robber problems — "rob houses 0 through n-2" and "rob houses 1 through n-1" — and take whichever gives more. Every legitimate circular plan is captured by one of those two linear slices, and neither slice can accidentally rob both wraparound neighbors.

🚩 Pattern-Recognition Cue

"Houses arranged in a circle" on top of the familiar House Robber phrasing is the cue: whenever a linear no-two-adjacent DP gets a wraparound constraint tacked on, the fix is almost always "run the linear version twice, once excluding each end, and take the max" rather than inventing a new circular recurrence from scratch.

🐢 Brute Force

Enumerate every subset of houses as a bitmask, keep only the subsets where no two adjacent bits are set and the first and last bits aren't both set (the circular adjacency), and take the max sum among valid subsets.

func robCircularBruteForce(_ nums: [Int]) -> Int {
    let n = nums.count
    guard n > 0 else { return 0 }
    guard n > 1 else { return nums[0] }

    var best = 0

    for mask in 0..<(1 << n) {
        var valid = true
        var sum = 0

        for i in 0..<n where valid {
            guard mask & (1 << i) != 0 else { continue }
            sum += nums[i]
            let next = (i + 1) % n   // wraps last house back to house 0
            if mask & (1 << next) != 0 {
                valid = false   // two adjacent houses robbed (possibly wrapping around)
            }
        }

        if valid {
            best = max(best, sum)
        }
    }

    return best
}

// smoke test
print(robCircularBruteForce([2, 3, 2]))       // 3
print(robCircularBruteForce([1, 2, 3, 1]))    // 4
print(robCircularBruteForce([1, 2, 3]))       // 3

Big-O: O(2^n · n) time — 2^n subsets, each requiring an O(n) scan to check adjacency (including the circular wrap) and sum the take. O(1) extra space beyond the loop variables.

🚀 Optimal

Run the ordinary linear House Robber rolling recurrence twice — once over houses 0...n-2 (excluding the last house) and once over houses 1...n-1 (excluding the first house) — and return the larger result.

func rob(_ nums: [Int]) -> Int {
    var prev2 = 0
    var prev1 = 0

    for num in nums {
        let current = max(prev1, prev2 + num)
        prev2 = prev1
        prev1 = current
    }

    return prev1
}

func robCircular(_ nums: [Int]) -> Int {
    let n = nums.count
    guard n > 0 else { return 0 }
    guard n > 1 else { return nums[0] }

    let excludeLast = Array(nums[0..<(n - 1)])
    let excludeFirst = Array(nums[1..<n])

    return max(rob(excludeLast), rob(excludeFirst))
}

// smoke test — same cases as the brute force
print(robCircular([2, 3, 2]))       // 3
print(robCircular([1, 2, 3, 1]))    // 4
print(robCircular([1, 2, 3]))       // 3

Big-O: O(n) time — two linear passes, each O(n), over slices that together cover O(n) total elements. O(n) space for the two array slices (or O(1) if the linear pass is written to take start/end indices instead of copying).

🔑 The Key Insight

The brute force treats the circular constraint literally, checking every one of the 2^n possible subsets against both the linear and the wraparound adjacency rule — correct, but paying an exponential price to rediscover something structural. The optimal version exploits a simple case split: since house 0 and the last house can never both appear in a valid answer, the circular problem is just two ordinary linear House Robber problems glued together by an outer max. Each of those linear problems is solved by the same O(n) rolling recurrence as plain House Robber — no new algorithm is needed, just running the old one twice on two overlapping-but-different slices and keeping the better result.

🔗 Related Chapters

  • 1D Dynamic Programming — the inner rob helper is the exact same two-state rolling recurrence from chapter 26's House Robber example, reused unchanged.
  • Arrays and Strings — excludeLast/excludeFirst are array slices, and the rolling pass over each is a plain left-to-right array traversal.

🧸 Memory Sentence

House Robber II is House Robber run twice — once pretending the last house doesn't exist, once pretending the first house doesn't exist — because a valid circular plan can never rob both wraparound neighbors at once.

✅ Check Your Understanding

  1. Why is it safe to solve "rob houses 0...n-2" and "rob houses 1...n-1" separately and just take the max, instead of needing a single recurrence that tracks whether house 0 was robbed?
  2. For nums = [2, 3, 2], trace both rob(excludeLast) and rob(excludeFirst) by hand. Which slice produces the winning answer of 3, and why can't robbing both house 0 and house 2 ever be valid here?
  3. What does robCircular return for nums.count == 1, and why does that case need to be handled before slicing (hint: what would nums[0..<(n-1)] and nums[1..<n] both look like if n == 1)?

⬅️ Previous: House Robber · Next: Longest Palindromic Substring ➡️

Clone this wiki locally