Pacific Atlantic Water Flow — Reverse DFS from Two Oceans (LC 417)
Sanjeev SharmaAdvertisement
Problem Statement
LeetCode 417 — Pacific Atlantic Water Flow (Medium)
There is an m x n rectangular island that borders the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). The island is partitioned into a grid of square cells, and heights[r][c] represents the height of the cell (r, c).
Water can flow from a cell to a neighboring cell whose height is less than or equal to the current cell's height. Return a list of grid coordinates from which rain water can flow to both the Pacific and Atlantic oceans.
Constraints:
m == heights.length,n == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
Example:
Input: 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]]Why This Problem Matters
Pacific Atlantic Water Flow is the definitive "reverse the search direction" interview problem. The brute-force approach — DFS from every cell to check if it reaches both oceans — is O((m times n)^2) and times out. The optimal solution flips the perspective: instead of asking "does this cell reach the ocean?", ask "which cells can the ocean reach if water flowed uphill?"
Google, Amazon, and Meta all rotate this problem through their on-site loops because it tests a specific cognitive skill: recognizing that an asymmetric search (any-to-target) becomes much cheaper when you swap roles (target-to-any). The same insight underlies LC 130 (Surrounded Regions), LC 1020 (Number of Enclaves), and LC 1162 (As Far From Land), forming a tight family of "boundary inversion" problems.
The Core Insight
The brute force checks each cell independently. The smart approach runs DFS from the ocean borders and reverses the height inequality. If water flows downhill from A to B when height[A] >= height[B], then in the reverse search we start at B and only step to neighbors with height >= height[B].
Concretely:
- Run DFS from every cell on the Pacific border (top row + left column). Mark every cell reachable as Pacific-reachable.
- Run DFS from every cell on the Atlantic border (bottom row + right column). Mark every cell reachable as Atlantic-reachable.
- The answer is every cell present in both sets.
Two boolean matrices — pacific[r][c] and atlantic[r][c] — track reachability. Each runs in O(m times n). Total: O(m times n). The intersection sweep is also linear.
Why does this give the correct answer? A cell can drain to the Pacific if and only if some path of non-increasing heights leads to a Pacific border cell. Equivalently, the cell is reachable from a Pacific border cell when stepping to non-decreasing heights. The reverse search finds exactly that set.
Visual Dry Run
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 4DFS from Pacific border (top + left). Starting from (0,0)=1, we can climb to (0,1)=2, (0,2)=2, (0,3)=3, (0,4)=5, etc. Marked cells pac:
P P P P P
P P P P P
P P P . .
P P . . .
P . . . .DFS from Atlantic border (bottom + right). Starting from (4,4)=4, climb to (3,4)=5, etc. Marked cells atl:
. . . . A
. . . A A
. . A A A
A A A A A
A A A A AIntersection:
. . . . X
. . . X X
. . X . .
X X . . .
X . . . .Answer: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]. Matches the expected output.
Solution (Optimal)
Python
class Solution:
def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
if not heights or not heights[0]:
return []
R, C = len(heights), len(heights[0])
pac = [[False] * C for _ in range(R)]
atl = [[False] * C for _ in range(R)]
def dfs(r: int, c: int, visited: list[list[bool]], prev: int) -> None:
# reverse flow: only walk into cells whose height >= prev
if (not (0 <= r < R and 0 <= c < C)
or visited[r][c]
or heights[r][c] < prev):
return
visited[r][c] = True
h = heights[r][c]
dfs(r + 1, c, visited, h)
dfs(r - 1, c, visited, h)
dfs(r, c + 1, visited, h)
dfs(r, c - 1, visited, h)
# 1) Pacific border: top row + left column
for r in range(R):
dfs(r, 0, pac, heights[r][0])
for c in range(C):
dfs(0, c, pac, heights[0][c])
# 2) Atlantic border: bottom row + right column
for r in range(R):
dfs(r, C - 1, atl, heights[r][C - 1])
for c in range(C):
dfs(R - 1, c, atl, heights[R - 1][c])
# 3) intersect
return [[r, c] for r in range(R) for c in range(C)
if pac[r][c] and atl[r][c]]JavaScript
/**
* @param {number[][]} heights
* @return {number[][]}
*/
var pacificAtlantic = function(heights) {
if (!heights.length || !heights[0].length) return [];
const R = heights.length, C = heights[0].length;
const pac = Array.from({ length: R }, () => Array(C).fill(false));
const atl = Array.from({ length: R }, () => Array(C).fill(false));
// reverse-flow DFS: only step where new height >= previous height
function dfs(r, c, visited, prev) {
if (r < 0 || r >= R || c < 0 || c >= C) return;
if (visited[r][c] || heights[r][c] < prev) return;
visited[r][c] = true;
const h = heights[r][c];
dfs(r + 1, c, visited, h);
dfs(r - 1, c, visited, h);
dfs(r, c + 1, visited, h);
dfs(r, c - 1, visited, h);
}
// Pacific: top row, left column
for (let r = 0; r < R; r++) dfs(r, 0, pac, heights[r][0]);
for (let c = 0; c < C; c++) dfs(0, c, pac, heights[0][c]);
// Atlantic: bottom row, right column
for (let r = 0; r < R; r++) dfs(r, C - 1, atl, heights[r][C - 1]);
for (let c = 0; c < C; c++) dfs(R - 1, c, atl, heights[R - 1][c]);
const result = [];
for (let r = 0; r < R; r++) {
for (let c = 0; c < C; c++) {
if (pac[r][c] && atl[r][c]) result.push([r, c]);
}
}
return result;
};Time Complexity: O(m times n) — each cell visited at most twice (once per ocean). Space Complexity: O(m times n) for visited matrices and recursion stack.
Common Mistakes
- Wrong inequality direction. Forward flow says
height[next] <= height[current]. Reverse flow saysheight[next] >= height[current]. Mixing them silently breaks the algorithm. - One DFS for both oceans. Each ocean needs its own visited matrix; sharing them mixes reachability sets.
- Forgetting corner cells. Corner cells (e.g.,
(0, C-1)) belong to both borders. They are seeded twice — fine, but a sanity check. - Allocating a new ocean DFS per cell. The DFS is cheap because each cell is marked visited; do not reset visited between border seeds.
- Using
<instead of<=in the strict comparison. The forward-flow rule is "less than or equal", so the reverse must be "greater than or equal" — equal heights are walkable.
Interview Tips
- State the inversion. "DFS from each cell to the ocean is O(N^2). DFS from each ocean to land is O(N) per ocean — that is the trick."
- Mention BFS as equivalent. Both DFS and BFS work; BFS uses a queue and slightly more memory but avoids stack overflow on large grids.
- Edge case: 1x1 grid. A single cell touches both oceans, so the answer is
[[0, 0]]. Mention this proactively.
Follow-up Questions
- What if water flows strictly downhill (
<instead of<=)? Same algorithm, switch to strict inequality everywhere. - What if there is a third ocean? Add a third visited matrix and intersect all three.
- What if heights can change dynamically? Re-run from scratch after each update, or use incremental updates with Union-Find on equal-height components.
- Find cells that drain to either ocean (not both)? Take the union of the two visited sets instead of the intersection.
Key Takeaways
- Pacific Atlantic Water Flow is the canonical reverse-flow problem: DFS from the oceans inward instead of from land outward.
- Reversing the height inequality (
<=becomes>=) is what makes the inversion correct. - Two visited matrices, one per ocean, then intersect them in a final sweep.
- The technique drops time from O((m times n)^2) to O(m times n).
- Both DFS and BFS work; choose based on stack depth concerns.
- The same boundary-inversion idea solves LC 130, LC 1020, and LC 1162 — recognize the family.
Advertisement
