LeetCode 417 · Medium · Graphs

Pacific Atlantic Water Flow

An island is a grid of heights. The Pacific touches its top and left edges, the Atlantic its bottom and right edges. Rain flows to a neighbour that is equal or lower. Return every cell whose water can reach both oceans.

O(m·n)time
O(m·n)space
DFS uphillfrom each ocean's border

rows separated by ; · heights 0–99 (digits run together, or separate with spaces) · 1–6 rows × 1–7 columns

Call stack dfs frames, bottom → top · the shaded path on the grid

private int rows;private int cols;private int[][] heights;public List<List<Integer>> pacificAtlantic(int[][] heights) { this.heights = heights; rows = heights.length; cols = heights[0].length; boolean[][] pac = new boolean[rows][cols]; boolean[][] atl = new boolean[rows][cols]; for (int c = 0; c < cols; c++) { dfs(0, c, pac, heights[0][c]); dfs(rows - 1, c, atl, heights[rows - 1][c]); } for (int r = 0; r < rows; r++) { dfs(r, 0, pac, heights[r][0]); dfs(r, cols - 1, atl, heights[r][cols - 1]); } List<List<Integer>> res = new ArrayList<>(); for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (pac[r][c] && atl[r][c]) { res.add(List.of(r, c)); } } } return res;}private void dfs(int r, int c, boolean[][] visit, int prevHeight) { if (r < 0 || c < 0 || r == rows || c == cols || visit[r][c] || heights[r][c] < prevHeight) { return; } visit[r][c] = true; dfs(r + 1, c, visit, heights[r][c]); dfs(r - 1, c, visit, heights[r][c]); dfs(r, c + 1, visit, heights[r][c]); dfs(r, c - 1, visit, heights[r][c]);}
visit
—
(r, c)
—
height
—
prevHeight
—
pac marked
0
atl marked
0

Why it works

  1. Brute force runs a search from every cell, flowing downhill, to see whether it reaches each ocean: O((m·n)²).
  2. Reverse the flow. Water reaches the Pacific from a cell exactly when you can climb from a Pacific border cell to it, moving only to equal or higher neighbours. So one uphill DFS from each ocean's border marks every cell that drains into it.
  3. O(m·n) time and space: each cell is marked in pac at most once and in atl at most once, and the answer is the intersection of the two grids.
  4. Pitfall: the comparison flips. Going uphill, a neighbour is allowed when heights[r][c] >= prevHeight; blocking on > instead drops plateaus of equal height, like the flat preset.
  5. Related: Surrounded Regions (130) uses the same "start from the border" trick to find what is connected to the edge.