Pacific Atlantic Water Flow
MediumGraphs
An island is cut into an m × n grid of cells, and heights[r][c] is the height of the cell in row r, column c, with row 0 at the top. The Pacific Ocean washes the top and left edges of the island; the Atlantic washes the bottom and right edges.
Rain on a cell runs to a neighboring cell (up, down, left or right) whenever that neighbor is no higher than the cell it leaves, and a cell on an edge drains straight into the ocean along that edge.
Return the [row, column] of every cell whose rain can reach both oceans. The cells can come back in any order.
Examples
Input: heights = [[1, 2, 3], [8, 9, 4], [7, 6, 5]] Output: [[0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
The 1 and the 2 in the top left are lower than everything around them except the Pacific, so their rain never reaches the Atlantic. Every other cell drains both ways.
Input: heights = [[4]] Output: [[0, 0]]
One cell touches all four edges, so it drains into both oceans.
Constraints
1 ≤ m, n ≤ 2000 ≤ heights[r][c] ≤ 10⁵
Stuck?
Hint 1
Following the rain downhill from every cell repeats a lot of work. Turn it around: start at each ocean’s edge and walk uphill to find every cell that drains into it.
Hint 2
Run one DFS or BFS from all the Pacific edge cells and one from all the Atlantic edge cells, stepping only to a neighbor at least as high. The answer is the cells both walks reach.
The idea
Following the rain downhill from every cell repeats the same paths over and over. Turn it around: start at an ocean's edge and walk uphill, stepping only to neighbours at least as high, and you reach exactly the cells whose rain drains into that ocean. Do that once for each ocean and keep the cells both walks reach.
Time O(m · n)Extra space O(m · n)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 6
climb marks in reached every cell it can reach uphill from starts. It begins by marking each start cell and putting it on the stack. A corner cell lies on two edges and can be listed twice, and the check keeps it from going on the stack twice.
function pacificAtlantic(heights) { const rows = heights.length; const cols = heights[0].length; const climb = (starts) => { const reached = heights.map((row) => row.map(() => false)); const stack = []; for (const [r, c] of starts) { if (!reached[r][c]) { reached[r][c] = true; stack.push([r, c]); } } while (stack.length) { const [r, c] = stack.pop(); for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const y = r + dr; const x = c + dc; if (y < 0 || y >= rows || x < 0 || x >= cols || reached[y][x]) continue; if (heights[y][x] >= heights[r][c]) { reached[y][x] = true; stack.push([y, x]); } } } return reached; }; const pacific = []; const atlantic = []; for (let r = 0; r < rows; r++) { pacific.push([r, 0]); atlantic.push([r, cols - 1]); } for (let c = 0; c < cols; c++) { pacific.push([0, c]); atlantic.push([rows - 1, c]); } const reachesPacific = climb(pacific); const reachesAtlantic = climb(atlantic); const out = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (reachesPacific[r][c] && reachesAtlantic[r][c]) out.push([r, c]); } } return out;}The trap
This version climbs only to a neighbour that is strictly higher, >. It looks right because water runs downhill, but rain also runs onto a neighbour of the same height. A cell whose only way to an ocean crosses two cells of equal height is never reached, so any grid with level ground on the way to an edge loses cells from the answer.
function pacificAtlantic(heights) { const rows = heights.length; const cols = heights[0].length; const climb = (starts) => { const reached = heights.map((row) => row.map(() => false)); const stack = []; for (const [r, c] of starts) { if (!reached[r][c]) { reached[r][c] = true; stack.push([r, c]); } } while (stack.length) { const [r, c] = stack.pop(); for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) { const y = r + dr; const x = c + dc; if (y < 0 || y >= rows || x < 0 || x >= cols || reached[y][x]) continue; if (heights[y][x] > heights[r][c]) { // strictly higher: water on a flat stretch is left out reached[y][x] = true; stack.push([y, x]); } } } return reached; }; const pacific = []; const atlantic = []; for (let r = 0; r < rows; r++) { pacific.push([r, 0]); atlantic.push([r, cols - 1]); } for (let c = 0; c < cols; c++) { pacific.push([0, c]); atlantic.push([rows - 1, c]); } const reachesPacific = climb(pacific); const reachesAtlantic = climb(atlantic); const out = []; for (let r = 0; r < rows; r++) { for (let c = 0; c < cols; c++) { if (reachesPacific[r][c] && reachesAtlantic[r][c]) out.push([r, c]); } } return out;}