Pacific Atlantic Water Flow
Find cells that can flow to both oceans.
Examples
Cells that can reach both Pacific (Top/Left) and Atlantic (Bottom/Right).
Problem Understanding
Water flows downhill (neighbor height <= current height).
- Pacific Ocean: Touches Left and Top edges.
- Atlantic Ocean: Touches Right and Bottom edges.
Find all coordinates (r, c) from which water can flow to BOTH oceans.
Algorithm Strategy (Backwards Flow)
Simulating flow from every cell is slow (O(MN * MN)).
Better Idea: Reverse the flow! Start from the Oceans and go uphill.
- Pacific Set: Run DFS from all Top/Left edges. Store reachable cells.
- Atlantic Set: Run DFS from all Bottom/Right edges. Store reachable cells.
- Result: The intersection of both sets.
Visualization
NUMBERS = HEIGHTS · PACIFIC: TOP + LEFT · ATLANTIC: BOTTOM + RIGHT · GREEN = BOTH
PACIFIC — TOP ROW
Pacific
0
Atlantic
0
Both
0
call stack · Pacific
No dfs running
Top row (0, 0) touches the Pacific: call dfs(0, 0) with prev = its own height, 1
Next
dfs(0, 0): height 1 ≥ 1 — it drains to the Pacific. Mark it
heights
Legend & Complexity
The cell whose dfs call is running
A marked cell whose call is waiting on a deeper one
Reached by the Pacific only
Reached by the Atlantic only
Reached by both oceans — part of the answer
Time
O(m·n)
Space
O(m·n) ocean grids and call stack
Both oceans climb in from their edges: the Pacific from the top row and left column, the Atlantic from the bottom row and right column, in the order the code calls them. A call returns if it leaves the grid, reaches a cell this ocean already reached, or would have to go downhill. Each ocean keeps its own colour; cells both oceans reach turn green, and the last pass collects them in row order.
Dry Run (3 by 3)
Heights (3 by 3):
1 2 3
2 5 2
3 2 1
| Step | Ocean | Starts from | Climbs | Cells reached |
|---|---|---|---|---|
| 1 | Pacific | top row 1, 2, 3 and left column 1, 2, 3 |
(0,1)=2 → (1,1)=5, since 5 ≥ 2. (0,2)=3 cannot climb to (1,2)=2, and (2,0)=3 cannot climb to (2,1)=2. |
(0,0), (0,1), (0,2), (1,0), (1,1), (2,0) |
| 2 | Atlantic | bottom row 3, 2, 1 and right column 3, 2, 1 |
(2,1)=2 → (1,1)=5. (2,0)=3 cannot climb to (1,0)=2, and (0,2)=3 cannot climb to (0,1)=2. |
(0,2), (1,1), (1,2), (2,0), (2,1), (2,2) |
| 3 | Both | — | Cells in both lists, in row order | [[0,2], [1,1], [2,0]] |
Edge Cases & Common Mistakes
- Flow Direction: The problem says water flows down. But our efficient solution flows up (from oceans). Ensure check is
height[new] >= height[curr]. - Visited Sets: Use two separate visited sets (or boolean grids) for Pacific and Atlantic.
- Single Cell Grid: Should return
[[0,0]](it touches all edges). - Flat Terrain: Water flows on equal heights too (
>=).
Solution
Two boolean grids, one per ocean, then every cell marked in both, in row order. Each answer is a list [r, c] — the Python version builds lists, not tuples, which is what LeetCode expects.
Pacific Atlantic Water Flow Code
1var pacificAtlantic = function(heights) {2 const rows = heights.length, cols = heights[0].length;3 const pacific = Array.from({ length: rows }, () => new Array(cols).fill(false));4 const atlantic = Array.from({ length: rows }, () => new Array(cols).fill(false));56 function dfs(r, c, ocean, prev) {7 if (r < 0 || r >= rows || c < 0 || c >= cols || ocean[r][c]) {8 return;9 }10 if (heights[r][c] < prev) {11 return;12 }13 ocean[r][c] = true;14 dfs(r + 1, c, ocean, heights[r][c]);15 dfs(r - 1, c, ocean, heights[r][c]);16 dfs(r, c + 1, ocean, heights[r][c]);17 dfs(r, c - 1, ocean, heights[r][c]);18 }1920 for (let c = 0; c < cols; c++) {21 dfs(0, c, pacific, heights[0][c]);22 dfs(rows - 1, c, atlantic, heights[rows - 1][c]);23 }24 for (let r = 0; r < rows; r++) {25 dfs(r, 0, pacific, heights[r][0]);26 dfs(r, cols - 1, atlantic, heights[r][cols - 1]);27 }2829 const result = [];30 for (let r = 0; r < rows; r++) {31 for (let c = 0; c < cols; c++) {32 if (pacific[r][c] && atlantic[r][c]) {33 result.push([r, c]);34 }35 }36 }37 return result;38};