LeetCode 417: Pacific Atlantic Water Flow (Reverse Multi-Source DFS/BFS)
LeetCode 417GraphMatrixToday we solve LeetCode 417 - Pacific Atlantic Water Flow.
Source: https://leetcode.com/problems/pacific-atlantic-water-flow/
English
Problem Summary
You are given a height matrix. Water can flow from a cell to its 4-neighbors if neighbor height is less than or equal to current height. Find all coordinates that can reach both the Pacific (top/left border) and Atlantic (bottom/right border).
Key Insight
Forward simulation from every cell is expensive. Reverse the perspective: start from ocean borders and move uphill (to neighbors with height greater than or equal to current). Cells reachable from Pacific in this reverse graph are exactly cells that can flow to Pacific in original direction; same for Atlantic. Intersect the two reachable sets.
Brute Force and Limitations
Brute force runs DFS/BFS from each cell to test if both oceans are reachable, costing up to O((mn)^2) in dense cases. This repeats traversals heavily and easily times out on larger grids.
Optimal Algorithm Steps
1) Create two visited matrices: pac, atl.
2) Run DFS/BFS from Pacific borders (row 0 and col 0), expanding only to neighbors with nextHeight >= curHeight.
3) Run DFS/BFS from Atlantic borders (row m-1 and col n-1) with same rule.
4) Collect coordinates where pac[r][c] && atl[r][c].
Complexity Analysis
Time: O(mn) (each cell visited at most once per ocean).
Space: O(mn) for visited matrices and recursion/queue.
Common Pitfalls
- Using forward edge condition in reverse traversal (should be next >= cur).
- Forgetting to seed all border cells for each ocean.
- Duplicating output when building results from two passes instead of intersection check.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
boolean[][] pac = new boolean[m][n];
boolean[][] atl = new boolean[m][n];
for (int r = 0; r < m; r++) {
dfs(heights, pac, r, 0);
dfs(heights, atl, r, n - 1);
}
for (int c = 0; c < n; c++) {
dfs(heights, pac, 0, c);
dfs(heights, atl, m - 1, c);
}
List<List<Integer>> ans = new ArrayList<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (pac[r][c] && atl[r][c]) ans.add(Arrays.asList(r, c));
}
}
return ans;
}
private void dfs(int[][] h, boolean[][] vis, int r, int c) {
int m = h.length, n = h[0].length;
if (vis[r][c]) return;
vis[r][c] = true;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (h[nr][nc] < h[r][c]) continue;
dfs(h, vis, nr, nc);
}
}
}func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
pac := make([][]bool, m)
atl := make([][]bool, m)
for i := 0; i < m; i++ {
pac[i] = make([]bool, n)
atl[i] = make([]bool, n)
}
var dfs func([][]bool, int, int)
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
dfs = func(vis [][]bool, r, c int) {
if vis[r][c] {
return
}
vis[r][c] = true
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n {
continue
}
if heights[nr][nc] < heights[r][c] {
continue
}
dfs(vis, nr, nc)
}
}
for r := 0; r < m; r++ {
dfs(pac, r, 0)
dfs(atl, r, n-1)
}
for c := 0; c < n; c++ {
dfs(pac, 0, c)
dfs(atl, m-1, c)
}
ans := [][]int{}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if pac[r][c] && atl[r][c] {
ans = append(ans, []int{r, c})
}
}
}
return ans
}class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> pac(m, vector<bool>(n, false));
vector<vector<bool>> atl(m, vector<bool>(n, false));
for (int r = 0; r < m; ++r) {
dfs(heights, pac, r, 0);
dfs(heights, atl, r, n - 1);
}
for (int c = 0; c < n; ++c) {
dfs(heights, pac, 0, c);
dfs(heights, atl, m - 1, c);
}
vector<vector<int>> ans;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (pac[r][c] && atl[r][c]) ans.push_back({r, c});
}
}
return ans;
}
private:
const vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
void dfs(const vector<vector<int>>& h, vector<vector<bool>>& vis, int r, int c) {
int m = h.size(), n = h[0].size();
if (vis[r][c]) return;
vis[r][c] = true;
for (auto [dr, dc] : dirs) {
int nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (h[nr][nc] < h[r][c]) continue;
dfs(h, vis, nr, nc);
}
}
};class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
pac = [[False] * n for _ in range(m)]
atl = [[False] * n for _ in range(m)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(vis: List[List[bool]], r: int, c: int) -> None:
if vis[r][c]:
return
vis[r][c] = True
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n:
continue
if heights[nr][nc] < heights[r][c]:
continue
dfs(vis, nr, nc)
for r in range(m):
dfs(pac, r, 0)
dfs(atl, r, n - 1)
for c in range(n):
dfs(pac, 0, c)
dfs(atl, m - 1, c)
ans = []
for r in range(m):
for c in range(n):
if pac[r][c] and atl[r][c]:
ans.append([r, c])
return ansvar pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length;
const pac = Array.from({ length: m }, () => Array(n).fill(false));
const atl = Array.from({ length: m }, () => Array(n).fill(false));
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
const dfs = (vis, r, c) => {
if (vis[r][c]) return;
vis[r][c] = true;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (heights[nr][nc] < heights[r][c]) continue;
dfs(vis, nr, nc);
}
};
for (let r = 0; r < m; r++) {
dfs(pac, r, 0);
dfs(atl, r, n - 1);
}
for (let c = 0; c < n; c++) {
dfs(pac, 0, c);
dfs(atl, m - 1, c);
}
const ans = [];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (pac[r][c] && atl[r][c]) ans.push([r, c]);
}
}
return ans;
};中文
题目概述
给定一个高度矩阵，水可以从当前格流向上下左右中高度小于等于当前格的相邻格。求所有既能流到太平洋（上边界/左边界）又能流到大西洋（下边界/右边界）的坐标。
核心思路
正向从每个点出发会重复很多遍。换个方向：从两大洋边界“反向爬坡”搜索，只能走到高度 >= 当前格的邻居。能被太平洋反向到达的点，等价于正向可流入太平洋；大西洋同理。最后取两个可达集合的交集。
暴力解法与不足
暴力做法是对每个格子都跑一次 DFS/BFS 判断能否到达两大洋，最坏接近 O((mn)^2)，大量重复遍历，数据稍大就会超时。
最优算法步骤
1）准备两个 visited：pac、atl。
2）从太平洋边界（第 0 行 + 第 0 列）做反向 DFS/BFS，条件是 nextHeight >= curHeight。
3）从大西洋边界（最后一行 + 最后一列）做同样遍历。
4）枚举所有格子，若 pac[r][c] && atl[r][c] 就加入答案。
复杂度分析
时间复杂度：O(mn)（每个格子每个海洋最多访问一次）。
空间复杂度：O(mn)（visited + 递归栈/队列）。
常见陷阱
- 反向遍历时条件写反（应是 next >= cur）。
- 边界初始化不完整，漏掉某条边。
- 结果合并方式错误，应取两个 visited 的交集。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
private static final int[][] DIRS = {{1,0},{-1,0},{0,1},{0,-1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
int m = heights.length, n = heights[0].length;
boolean[][] pac = new boolean[m][n];
boolean[][] atl = new boolean[m][n];
for (int r = 0; r < m; r++) {
dfs(heights, pac, r, 0);
dfs(heights, atl, r, n - 1);
}
for (int c = 0; c < n; c++) {
dfs(heights, pac, 0, c);
dfs(heights, atl, m - 1, c);
}
List<List<Integer>> ans = new ArrayList<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (pac[r][c] && atl[r][c]) ans.add(Arrays.asList(r, c));
}
}
return ans;
}
private void dfs(int[][] h, boolean[][] vis, int r, int c) {
int m = h.length, n = h[0].length;
if (vis[r][c]) return;
vis[r][c] = true;
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (h[nr][nc] < h[r][c]) continue;
dfs(h, vis, nr, nc);
}
}
}func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
pac := make([][]bool, m)
atl := make([][]bool, m)
for i := 0; i < m; i++ {
pac[i] = make([]bool, n)
atl[i] = make([]bool, n)
}
var dfs func([][]bool, int, int)
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
dfs = func(vis [][]bool, r, c int) {
if vis[r][c] {
return
}
vis[r][c] = true
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= m || nc < 0 || nc >= n {
continue
}
if heights[nr][nc] < heights[r][c] {
continue
}
dfs(vis, nr, nc)
}
}
for r := 0; r < m; r++ {
dfs(pac, r, 0)
dfs(atl, r, n-1)
}
for c := 0; c < n; c++ {
dfs(pac, 0, c)
dfs(atl, m-1, c)
}
ans := [][]int{}
for r := 0; r < m; r++ {
for c := 0; c < n; c++ {
if pac[r][c] && atl[r][c] {
ans = append(ans, []int{r, c})
}
}
}
return ans
}class Solution {
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
int m = heights.size(), n = heights[0].size();
vector<vector<bool>> pac(m, vector<bool>(n, false));
vector<vector<bool>> atl(m, vector<bool>(n, false));
for (int r = 0; r < m; ++r) {
dfs(heights, pac, r, 0);
dfs(heights, atl, r, n - 1);
}
for (int c = 0; c < n; ++c) {
dfs(heights, pac, 0, c);
dfs(heights, atl, m - 1, c);
}
vector<vector<int>> ans;
for (int r = 0; r < m; ++r) {
for (int c = 0; c < n; ++c) {
if (pac[r][c] && atl[r][c]) ans.push_back({r, c});
}
}
return ans;
}
private:
const vector<pair<int,int>> dirs = {{1,0},{-1,0},{0,1},{0,-1}};
void dfs(const vector<vector<int>>& h, vector<vector<bool>>& vis, int r, int c) {
int m = h.size(), n = h[0].size();
if (vis[r][c]) return;
vis[r][c] = true;
for (auto [dr, dc] : dirs) {
int nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (h[nr][nc] < h[r][c]) continue;
dfs(h, vis, nr, nc);
}
}
};class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
pac = [[False] * n for _ in range(m)]
atl = [[False] * n for _ in range(m)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(vis: List[List[bool]], r: int, c: int) -> None:
if vis[r][c]:
return
vis[r][c] = True
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if nr < 0 or nr >= m or nc < 0 or nc >= n:
continue
if heights[nr][nc] < heights[r][c]:
continue
dfs(vis, nr, nc)
for r in range(m):
dfs(pac, r, 0)
dfs(atl, r, n - 1)
for c in range(n):
dfs(pac, 0, c)
dfs(atl, m - 1, c)
ans = []
for r in range(m):
for c in range(n):
if pac[r][c] and atl[r][c]:
ans.append([r, c])
return ansvar pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length;
const pac = Array.from({ length: m }, () => Array(n).fill(false));
const atl = Array.from({ length: m }, () => Array(n).fill(false));
const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
const dfs = (vis, r, c) => {
if (vis[r][c]) return;
vis[r][c] = true;
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
if (heights[nr][nc] < heights[r][c]) continue;
dfs(vis, nr, nc);
}
};
for (let r = 0; r < m; r++) {
dfs(pac, r, 0);
dfs(atl, r, n - 1);
}
for (let c = 0; c < n; c++) {
dfs(pac, 0, c);
dfs(atl, m - 1, c);
}
const ans = [];
for (let r = 0; r < m; r++) {
for (let c = 0; c < n; c++) {
if (pac[r][c] && atl[r][c]) ans.push([r, c]);
}
}
return ans;
};
Comments