Pacific Atlantic Water Flow
The Prompt
There is an `m x n` rectangular island that borders both the Pacific Ocean and the Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. You are given an `m x n` integer matrix `heights` where `heights[r][c]` represents the height of the cell `(r, c)`. Water can flow from any cell to an adjacent cell with an equal or lower height. Return a 2D list of grid coordinates `result` where `result[i] = [ri, ci]` denotes that rain water can flow from cell `(ri, ci)` to both the Pacific and Atlantic oceans.
Understanding the Problem
Tracing water downhill from every cell to see whether it reaches each ocean repeats enormous amounts of work — many cells share the same downhill paths. The reframe: work backwards from the oceans. A cell can drain to the Pacific exactly when the Pacific can be reached from it going downhill — equivalently, when the cell is reachable from a Pacific-border cell walking uphill-or-equal.
So run two traversals: one seeded from all Pacific-border cells (top row and left column), one from all Atlantic-border cells (bottom row and right column), each expanding only into neighbors with height greater than or equal to the current cell. The answer is the intersection of the two reachable sets.
The Interview Flow
Interviewer
Given a grid of heights, how do you find all cells from which water can flow to both the Pacific (top/left) and Atlantic (bottom/right) oceans?
Candidate
Trying to trace the path of water from every single cell outwards would be very inefficient and repetitive. It seems better to work backwards.
Interviewer
What do you mean by backwards?
Candidate
Instead of seeing where water can flow *to* from a cell, I can see which cells can flow *from* the oceans. I can start a traversal (like DFS) from all the cells bordering the Pacific and find all the cells that are reachable from them. I'll store these in a "pacific_reachable" set. Then, I'll do the same thing for the Atlantic ocean and store those in an "atlantic_reachable" set.
Interviewer
How does the water flow rule affect this reverse traversal?
Candidate
Since I'm going backwards, from the ocean inland, water can "flow" from a cell to an adjacent cell if the adjacent cell's height is greater than or equal to the current cell's height. It's the reverse of the original problem statement.
Interviewer
And the final answer?
Candidate
The final answer will be the intersection of the two sets: `pacific_reachable` and `atlantic_reachable`. Any cell that is in both sets can reach both oceans.
Interviewer
This is a very elegant solution. It avoids redundant computations by starting from the edges. Please implement it.
Why does reversing the flow direction turn this into two cheap traversals?
The invariant of each traversal: a cell is marked exactly when there is a non-increasing height path from it to that ocean's border. The reversed edge rule (move only to neighbors with height ≥ current) is precisely the original flow rule read backwards, so the marked set equals the true drainage set — no per-cell path tracing needed.
Each traversal visits every cell at most once, so the whole algorithm is two O(m · n) passes plus an O(m · n) intersection — versus the naive approach's traversal from every one of the m · n cells. Space is O(m · n) for the two visited sets.
Reverse Flow from Oceans using DFS
- Initialize two sets, `pacific` and `atlantic`, to store the coordinates of cells reachable from each ocean.
- Get the dimensions of the grid, `rows` and `cols`.
- Define a `dfs` helper function that takes a cell `(r,c)`, a `visited` set, and the `prevHeight`.
- **Inside `dfs`:** Check for out of bounds, already visited, or if the current cell height is less than `prevHeight`. If any are true, return. Otherwise, add `(r,c)` to `visited` and recurse on all four neighbors with the current cell's height as the new `prevHeight`.
- Iterate through the top and bottom rows:
- - Call `dfs` for each cell in the top row, passing the `pacific` set.
- - Call `dfs` for each cell in the bottom row, passing the `atlantic` set.
- Iterate through the left and right columns:
- - Call `dfs` for each cell in the left column, passing the `pacific` set.
- - Call `dfs` for each cell in the right column, passing the `atlantic` set.
- Finally, iterate through the grid and find all cells `(r,c)` that exist in both the `pacific` and `atlantic` sets. Add these to your result list.
Try it yourself
Write your solution and run it against 2 test cases.
JavaScript, TypeScript & Python run sandboxed in your browser; other languages run on the execution server. Your code is saved locally as you type.
Final Solution
function pacificAtlantic(heights) {
const rows = heights.length, cols = heights[0].length;
const pacific = new Set(), atlantic = new Set();
const res = [];
function dfs(r, c, visited, prevHeight) {
const key = `${r},${c}`;
if (r < 0 || c < 0 || r >= rows || c >= cols || visited.has(key) || heights[r][c] < prevHeight) {
return;
}
visited.add(key);
dfs(r + 1, c, visited, heights[r][c]);
dfs(r - 1, c, visited, heights[r][c]);
dfs(r, c + 1, visited, heights[r][c]);
dfs(r, c - 1, visited, heights[r][c]);
}
for (let c = 0; c < cols; c++) {
dfs(0, c, pacific, heights[0][c]);
dfs(rows - 1, c, atlantic, heights[rows - 1][c]);
}
for (let r = 0; r < rows; r++) {
dfs(r, 0, pacific, heights[r][0]);
dfs(r, cols - 1, atlantic, heights[r][cols - 1]);
}
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
const key = `${r},${c}`;
if (pacific.has(key) && atlantic.has(key)) {
res.push([r, c]);
}
}
}
return res;
}Explanation
heights = [[1,2,2],[3,5,4]]: Pacific touches the top and left edges, Atlantic the bottom and right.
1The grid as a graph of the six cells (top row 1, 2, 2; bottom row 3, 5, 4). The Pacific traversal is seeded with every top-row and left-column cell: 1, 2, 2, and 3 all start marked P.
2Expand uphill-or-equal: from the 2 at the top we can step to the 5 below (5 ≥ 2), and from the other 2 to the 4 below (4 ≥ 2). All six cells can drain to the Pacific.
3The Atlantic traversal seeds the bottom row (3, 5, 4) and right column (the 2 at top-right), then expands one step: top-right 2 → top-middle 2 (2 ≥ 2). It cannot reach the 1 (1 < 2). Intersection: five cells — every cell except the 1.
Complexity Analysis
TIME
O(m*n)
SPACE
O(m*n)
Finished working through this one?
Mark it complete to track it on your Data Structures path.