Pacific Atlantic Water Flow
Medium Reverse BFS/DFS from the oceans
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rain flows from a cell to neighbours with equal or lower height. The Pacific touches the top and left edges, the Atlantic the bottom and right. Return cells from which water can reach both oceans.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: cells from which water can reach both oceans.
Why this works: flip it: start from each ocean's edge and climb uphill. Cells reached from both oceans are the answer.
Example: a high peak in the middle of the grid
reachable uphill from the top/left edge and from the bottom/right edge → included✦Hints open one at a time
↗Approach
DFS from all Pacific edge cells moving to neighbours with height >= current; same for the Atlantic. Cells marked by both are the answer.
</>Solution (Java)
import java.util.*;
class Solution {
private int m, n;
private int[][] h;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
h = heights;
m = h.length;
n = h[0].length;
boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
for (int r = 0; r < m; r++) {
climb(r, 0, pac);
climb(r, n - 1, atl);
}
for (int c = 0; c < n; c++) {
climb(0, c, pac);
climb(m - 1, c, atl);
}
List<List<Integer>> res = new ArrayList<>();
for (int r = 0; r < m; r++)
for (int c = 0; c < n; c++)
if (pac[r][c] && atl[r][c]) res.add(Arrays.asList(r, c));
return res;
}
private void climb(int r, int c, boolean[][] seen) {
if (seen[r][c]) return;
seen[r][c] = true;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nc >= 0 && nr < m && nc < n && h[nr][nc] >= h[r][c]) climb(nr, nc, seen); // uphill only
}
}
}!Common mistake
Using < instead of >= when climbing — equal heights also let water flow.
- Time: O(m·n).
- Space: O(m·n).