House Robber

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

1. Core Invariant / The Trick

At house `x`, either skip (`rob2`) or rob `x` + best two houses back (`rob1 + x`). Recurrence `nxt = max(rob2, rob1 + x)` collapses strictly into two rolling variables.

2. Complexity Bounds & Proof

Single linear pass updating two variables representing `dp[i-2]` and `dp[i-1]`.

3. Minimal Idiomatic Code

def rob(nums: list[int]) -> int:
    rob1 = rob2 = 0
    for x in nums:
        rob1, rob2 = rob2, max(rob2, rob1 + x)
    return rob2

4. Failure Modes & Interview Follow-ups

Pitfalls:- Greedily choosing odd vs even indices fails `[2, 1, 1, 2] -> 4`.
Follow-ups:- House Robber II wraps around on a circle by taking `max(robLinear(nums[1:]), robLinear(nums[:-1]))`.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

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