Trapping Rain Water

hardTests passed 2026-11-11v1.0.0
TC: O(N)|SC: O(1)
Two PointersOriginal Statement (leetcode).md

1. Core Invariant / The Trick

Water above bar `i` equals `min(maxLeft, maxRight) - height[i]`. Using two pointers maintaining `leftMax` and `rightMax`, whenever `leftMax <= rightMax`, the right side is guaranteed >= `leftMax`, so water at `l` is finalized cleanly in O(1) space!

2. Complexity Bounds & Proof

Because `leftMax` and `rightMax` are non-decreasing prefixes/suffixes, the smaller side always safely determines `min(maxLeft, maxRight)` at its frontier.

3. Minimal Idiomatic Code

def trap(height: list[int]) -> int:
    l, r = 0, len(height) - 1
    l_max = r_max = 0
    water = 0
    while l < r:
        if height[l] < height[r]:
            l_max = max(l_max, height[l])
            water += l_max - height[l]
            l += 1
        else:
            r_max = max(r_max, height[r])
            water += r_max - height[r]
            r -= 1
    return water

4. Failure Modes & Interview Follow-ups

Pitfalls:- Updating `leftMax` before computing `leftMax - height[l]` ensures non-negative water clamped naturally at 0.
Follow-ups:- 2D Trapping Rain Water II requires a min-heap prioritizing the lowest perimeter boundary.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

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

Related Invariants

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