Pacific Atlantic Water Flow medium
Description
You are given an m x n integer matrix heights representing the height of each unit cell in a continent. The Pacific Ocean touches the left and top edges; the Atlantic Ocean touches the right and bottom edges. Rain water can flow from a cell to a neighboring cell (4-directionally adjacent) if the neighbor’s height is less than or equal to the cell’s height.
Return a list of all grid coordinates (r, c) from which water can flow to both oceans.
Examples
> Case 1:
heights = [
[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]
]
Output: [[0,4], [1,3], [1,4], [2,2], [3,0], [3,1], [4,0]]
> Case 2:
heights = [[1]]
Output: [[0, 0]] # the single cell touches both oceansConstraints
1 <= m, n <= 2000 <= heights[i][j] <= 10^5
The naive approach (slow)
For every cell, run BFS / DFS and check whether it can reach the Pacific AND the Atlantic. That’s O(m·n · m·n) = O((mn)²) — for a 200×200 grid, that’s 1.6 billion operations. Will TLE.
The reverse-flood trick
Flip the problem on its head. Instead of asking “can water flow from cell X to the ocean,” ask “which cells can the ocean reach if we flow water uphill from it?”
If we start from every Pacific-edge cell and “flow uphill” (visiting neighbors that are ≥ current height), we mark every cell that drains into the Pacific. Do the same for the Atlantic. The answer is the intersection — cells reachable from both.
Reverse-flooding is just multi-source BFS / DFS with the inequality flipped.
Algorithm
1. Initialize two visited sets: pacific = {}, atlantic = {}
2. From every Pacific-edge cell (top row + left column),
DFS with "uphill" rule (heights[neighbor] >= heights[current]).
Add all visited cells to pacific.
3. Same for Atlantic-edge cells (bottom row + right column) → atlantic.
4. Return the intersection: cells in both pacific and atlantic.Code
The “reverse-flood from the boundary” trick is one of the most reusable grid-graph patterns. The same idea solves Surrounded Regions (anchor from the boundary) and “Number of Closed Islands” (don’t count islands touching the boundary).
Mental model: when the question is “which cells satisfy a global reachability property”, ask whether it’s easier to flood from the property-satisfier and mark everything it touches.
Why it’s O(m·n) total
Each cell is visited at most twice — once in the Pacific DFS, once in the Atlantic DFS. Each visit looks at 4 neighbors. Total work: O(m·n). The reverse-flood collapses the naive O((mn)²) into linear.
Variants
| Problem | Twist |
|---|---|
| Surrounded Regions | Anchor from the boundary, mark all “safe” Os. |
| Number of Closed Islands | Same anchor-from-boundary trick. |
| Number of Enclaves | Count cells unreachable from the boundary. |
| As Far From Land as Possible | Multi-source BFS from all land cells. |
The boundary is your friend — when you have an “edge effect” condition, start there.
Analysis
- Time: O(m · n) — each cell visited at most twice.
- Space: O(m · n) for the two visited matrices + recursion stack.