House Robber II

mediumTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
1D DPOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Since house `0` and `n-1` are adjacent in a circle, they cannot both be robbed. Split into two linear House Robber subproblems excluding either endpoint: `max(nums[0], linear(nums[:-1]), linear(nums[1:]))`.

2. Complexity Bounds & Proof

Two linear passes over `N - 1` slices in O(1) space.

3. Minimal Idiomatic Code

def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]
    def lin(arr):
        a = b = 0
        for x in arr:
            a, b = b, max(b, a + x)
        return b
    return max(lin(nums[:-1]), lin(nums[1:]))

4. Failure Modes & Interview Follow-ups

Pitfalls:- Length-1 array (`[5]`): slicing `nums[:-1]` and `nums[1:]` both yield empty `[]`, returning `0` unless guarded by `if len(nums) == 1: return nums[0]`.
Follow-ups:- House Robber III solves the same non-adjacent constraint on a Binary Tree.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

House Robber (O(N))
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.