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 oceansIn plain English, we are given a 2D matrix of integers representing the height of terrain. The top and left borders of the matrix touch the "Pacific Ocean". The bottom and right borders touch the "Atlantic Ocean". Water can flow from a cell to any orthogonally adjacent cell with an equal or lower height. We need to find all grid coordinates where a drop of water placed on that cell could eventually flow to both the Pacific and the Atlantic oceans. Constraints: grid dimensions up to 200x200, heights up to 10^5.
The 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.
The ELI5 Analogy
Imagine dropping a water balloon on every single square of a massive hilly island and tracking where the water goes to see if it reaches both beaches. This is exhausting and repetitive. Instead, imagine reversing gravity slightly. Picture a massive wave from the Pacific Ocean sweeping inland, climbing up any hill that isn't too steep (meaning equal or higher elevation). We color everything it touches blue. Then we imagine a wave from the Atlantic sweeping inland, coloring everything it touches red. The spots that are colored purple (both blue and red) are the spots that could have drained to both!
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.
Code Walkthrough & Trace
Consider a tiny 2x2 grid:
1 2
3 4- Pacific touches Top (1, 2) and Left (1, 3).
- Atlantic touches Bottom (3, 4) and Right (2, 4).
| Step | Action | pacific set | atlantic set |
|---|---|---|---|
| 1 | Seed Pacific Top edge: (0,0)[val=1], (0,1)[val=2] | {(0,0), (0,1)} | {} |
| 2 | Seed Pacific Left edge: (0,0)[done], (1,0)[val=3] | {(0,0), (0,1), (1,0)} | {} |
| 3 | Pacific DFS climbs. (0,1)[val=2] climbs to (1,1)[val=4]. (1,0)[val=3] climbs to (1,1)[val=4]. | {(0,0), (0,1), (1,0), (1,1)} | {} |
| 4 | Seed Atlantic Bottom edge: (1,0)[val=3], (1,1)[val=4] | ... | {(1,0), (1,1)} |
| 5 | Seed Atlantic Right edge: (0,1)[val=2], (1,1)[done] | ... | {(1,0), (1,1), (0,1)} |
| 6 | Atlantic DFS climbs. (1,0)[val=3] CANNOT climb to (0,0)[val=1] (it's lower!). | ... | ... |
| 7 | Result intersection pacific & atlantic | {(0,1), (1,0), (1,1)} |
Key lines explained:
if heights[r][c] < prev_height: return- This is the uphill check! If the new cell is lower than where we came from, the "ocean wave" cannot wash over it, so we stop.climb(0, c, pacific, heights[0][c])- We pass the cell's own height asprev_heightto instantly pass the uphill check on the first step, effectively bootstrapping the DFS.
Complexity
O(rows \times cols) time. Each cell is visited at most once per ocean, so at most twice overall. To break it down: we do two completely separate DFS passes. The first DFS (Pacific) visits cells, adds them to a set, and never visits them again. In the absolute worst case (an island shaped like a bowl where the whole thing is reachable), it visits all N cells. The second DFS (Atlantic) does the same. Total operations are proportional to 2N, which simplifies to O(N).
O(rows \times cols) space for the two sets and the recursion. The sets store at most N elements each. The recursion call stack can go N deep.
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.