Pacific Atlantic Water Flow
mediumTests passed 2026-11-11v1.0.01. Core Invariant / The Trick
Reverse flow from the coastlines uphill (`nextHeight >= currHeight`) instead of running downhill DFS from every cell. Intersect the Pacific-reachable set (`pac`) with the Atlantic-reachable set (`atl`).
2. Complexity Bounds & Proof
Two uphill traversals visit each cell at most once per ocean, reducing O((MN)^2) to linear grid time.
3. Minimal Idiomatic Code
def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
R, C = len(heights), len(heights[0])
def dfs(r, c, seen, prev_h):
if not (0 <= r < R and 0 <= c < C) or (r, c) in seen or heights[r][c] < prev_h:
return
seen.add((r, c))
h = heights[r][c]
dfs(r + 1, c, seen, h); dfs(r - 1, c, seen, h)
dfs(r, c + 1, seen, h); dfs(r, c - 1, seen, h)
pac, atl = set(), set()
for c in range(C):
dfs(0, c, pac, 0)
dfs(R - 1, c, atl, 0)
for r in range(R):
dfs(r, 0, pac, 0)
dfs(r, C - 1, atl, 0)
return [[r, c] for r, c in (pac & atl)]4. Failure Modes & Interview Follow-ups
Pitfalls:- Traversing downhill from every cell repeats work across shared valleys.
- Remember reverse flow uses `>=` (`heights[nr][nc] >= heights[r][c]`), not `<=`.
Follow-ups:- Trapping Rain Water II generalizes perimeter inward elevation propagation with a min-heap.
Personal Notes & Scratchpad (Local-First Yjs CRDT)
Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.
Related Invariants
Browser Scratchpad
Console Output
Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.