417 · Pacific Atlantic Water Flow

Asked forwards — from this cell, can water reach both oceans? — every cell needs its own traversal: O((mn)²). Asked backwards — which cells can each ocean reach if water flowed uphill? — it is one flood from Pacific, one flood from Atlantic, and the answer is the intersection.

Execution

idle

INVARIANT Reverse Ocean Invariant: Simulating water downhill from every interior cell is O((mn)²). Reverse the flow: start at ocean borders and flood UPHILL (h[next] ≥ h[curr]). Cells reached by BOTH floods (pac && atl) form the intersection!

Pacific

Atlantic

Press Run to begin.

0 / 0

Speed

Java · running line

Pacific reaches it Atlantic reaches it both — solution in queue neither

INTERVIEW SCRIPT

How to Explain Pacific Atlantic Water Flow to an Interviewer

1. Discard the Forward Simulation

"Simulating water flowing downhill from each interior cell forces us to restart traversal from scratch for each cell, resulting in $O((m \cdot n)^2)$ time."

2. Reverse the Perspective (Uphill Flow)

"Instead, think: where could the water have come from? Start at ocean edges and flood uphill. The neighbor condition inverts: step to (nr, nc) only if heights[nr][nc] ≥ heights[r][c]."

3. Two Independent Ocean Sweeps

"Run one multi-source BFS/DFS seeded with Pacific borders (top row + left column) into boolean[][] pac, and a second seeded with Atlantic borders (bottom row + right column) into boolean[][] atl."

4. Set Intersection

"Any coordinate where pac[r][c] && atl[r][c] can drain to both oceans. Time is strictly $O(m \cdot n)$ and auxiliary space is $O(m \cdot n)$."

O(m·n) time, O(m·n) space · two floods instead of mn of them. Answers are returned sorted by row, then column. Walking out from the ocean is walking against the water, so the comparison inverts: h[next] >= h[cur].