Appearance
4.20.4 — Pacific Atlantic Water Flow
LeetCode 417 · Medium · ★ Blind 75
The problem
A grid of heights. The Pacific touches the top and left edges; the Atlantic touches the bottom and right edges. Water flows from a cell to a neighbour of equal or lower height. Return every cell from which water can reach both oceans.
1 2 2 3 (5)
3 2 3(4)(4)
2 4 (5) 3 1
(6)(7) 1 4 5
(5) 1 1 2 4
the bracketed cells reach both oceansThe pattern
The obvious approach is to start at each cell and see whether water can escape to each ocean. That is a search per cell, so O((rows \times cols)^2), and it repeats enormous amounts of work.
Turn it round.
Instead of asking which cells can reach the ocean, ask which cells the ocean can reach — by walking uphill from the edges.
Water flows downhill from a cell to the sea. So the sea, walking backwards, moves upward or level. Start a search at every Pacific edge cell and climb; everything it reaches is a cell that could drain to the Pacific. Do the same for the Atlantic. The answer is the intersection of the two sets.
Two searches instead of rows × cols searches. Reversing the direction of a search is one of the most reliable tricks in graph problems, and this is its clearest example.
The solution
python
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
if not heights:
return []
rows, cols = len(heights), len(heights[0])
pacific, atlantic = set(), set()
def climb(r: int, c: int, seen: set, prev_height: int):
if (r, c) in seen:
return
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if heights[r][c] < prev_height: # water cannot flow uphill to here
return
seen.add((r, c))
h = heights[r][c]
climb(r + 1, c, seen, h)
climb(r - 1, c, seen, h)
climb(r, c + 1, seen, h)
climb(r, c - 1, seen, h)
for c in range(cols):
climb(0, c, pacific, heights[0][c]) # top edge
climb(rows - 1, c, atlantic, heights[rows - 1][c]) # bottom edge
for r in range(rows):
climb(r, 0, pacific, heights[r][0]) # left edge
climb(r, cols - 1, atlantic, heights[r][cols - 1]) # right edge
return [[r, c] for r, c in pacific & atlantic]ts
function pacificAtlantic(heights: number[][]): number[][] {
if (!heights.length) return [];
const rows = heights.length, cols = heights[0].length;
const pacific = new Set<string>(), atlantic = new Set<string>();
function climb(r: number, c: number, seen: Set<string>, prev: number): void {
const key = `${r},${c}`;
if (r < 0 || r >= rows || c < 0 || c >= cols) return;
if (seen.has(key)) return;
if (heights[r][c] < prev) return;
seen.add(key);
const h = heights[r][c];
climb(r + 1, c, seen, h); climb(r - 1, c, seen, h);
climb(r, c + 1, seen, h); climb(r, c - 1, seen, h);
}
for (let c = 0; c < cols; c++) {
climb(0, c, pacific, heights[0][c]);
climb(rows - 1, c, atlantic, heights[rows - 1][c]);
}
for (let r = 0; r < rows; r++) {
climb(r, 0, pacific, heights[r][0]);
climb(r, cols - 1, atlantic, heights[r][cols - 1]);
}
const result: number[][] = [];
for (const key of pacific) if (atlantic.has(key)) {
const [r, c] = key.split(',').map(Number);
result.push([r, c]);
}
return result;
}heights[r][c] < prev_height is the reversed flow condition. Going forwards, water moves to a neighbour of equal or lower height. Going backwards, you may only move to a neighbour of equal or greater height — so a lower neighbour is rejected.
Each edge cell is seeded with its own height, so the first comparison always passes and the search starts.
Two separate visited sets, one per ocean. A cell may be reachable from one and not the other, and sharing a set would conflate them.
Corner cells belong to both oceans and are seeded twice. Nothing special is needed — the seen check handles the repeat.
In TypeScript the visited set is keyed by a string, because a Set compares arrays by identity and [0,1] would never match another [0,1]. Encoding as "0,1" or as r * cols + c fixes it. Python tuples are hashable by value, so (r, c) works directly. This is the same trap as 4.4.4.
Complexity
O(rows \times cols) time. Each cell is visited at most once per ocean, so at most twice overall.
O(rows \times cols) space for the two sets and the recursion.
Compare with the naive per-cell search at O((rows \times cols)^2) — on a 200×200 grid that is 1.6 billion operations against 80,000.
Where this goes next
The idea of reversing the search direction shows up whenever "who can reach the target" is asked for many sources at once:
- Surrounded Regions — instead of finding regions that do not touch the border, find the ones that do, and everything else is surrounded. 4.20.5.
- Rotting Oranges and Walls and Gates — start from every source at once rather than searching from every target. 4.20.6, 4.20.7.
- Reverse a directed graph to answer "which nodes can reach X" with one search instead of one per node.
The tell: the question asks about many sources reaching a few targets. Flip it into few sources reaching many, and one search replaces thousands.
What the interviewer will push on
"Why search from the oceans instead of from each cell?" Two searches instead of rows × cols searches. Give both complexities.
"What is the flow condition when reversed?" You may move to a neighbour of equal or greater height, because water came down that way.
"Why two visited sets?" A cell may reach one ocean and not the other.
"How do you handle the corners?" They are seeded for both oceans; the visited check makes the repeat harmless.
"Why not use an array as a set key in JavaScript?" Identity comparison. Encode the coordinates.
One thing to volunteer: name the reversal explicitly. "Water flows downhill to the sea, so I walk uphill from the sea." That one sentence is the entire insight, and saying it before coding makes everything after it obvious.
Next: 4.20.5 Surrounded Regions — the same reversal, used to mark survivors.