LeetCode 417 ·
Medium
Pacific Atlantic Water Flow
Find cells from which water can flow to both the Pacific and Atlantic borders.
Try it
Step through the core mechanic. The simulator below runs the dfs shape this problem is built on.
Interactive · grid flood-fill
◦
~
~
~
~
~
~
~
~
~
~
stack (bottom → top)
(0,0)
seed the stack with the start cell (0,0)
BFS vs DFS, same grid.
Swap the frontier from a queue to a stack and breadth-first becomes depth-first.
Both visit exactly the same cells; only the order differs. BFS layers outward
(shortest-path / wave problems); DFS plunges down one branch (component / path problems).
The approach
Invert the problem: DFS inward from each ocean's border, marking cells that can reach it (climbing to equal-or-higher neighbours). The answer is the intersection of the two reachable sets.
| Aspect | Value |
|---|---|
| Pattern | DFS |
| Recognise it by | Cells draining to both oceans. |
| Time complexity | O(mn) |
| Space complexity | O(mn) |
| Difficulty | Medium |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.