# Pacific Atlantic Water Flow

- **Canonical ID**: `pacific-atlantic-water-flow`
- **Canonical URL**: https://dsacheatsheet.com/problems/pacific-atlantic-water-flow
- **Difficulty**: medium
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/pacific-atlantic-water-flow/

## 1. Core Invariant / The Trick

Reverse flow from the coastlines uphill (`nextHeight >= currHeight`) instead of running downhill DFS from every cell. Intersect the Pacific-reachable set (`pac`) with the Atlantic-reachable set (`atl`).

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(M * N)`
- **Space Complexity**: `O(M * N)`
- **Proof**: Two uphill traversals visit each cell at most once per ocean, reducing O((MN)^2) to linear grid time.

## 3. Minimal Idiomatic Code

### Python
```python
def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    R, C = len(heights), len(heights[0])
    def dfs(r, c, seen, prev_h):
        if not (0 <= r < R and 0 <= c < C) or (r, c) in seen or heights[r][c] < prev_h:
            return
        seen.add((r, c))
        h = heights[r][c]
        dfs(r + 1, c, seen, h); dfs(r - 1, c, seen, h)
        dfs(r, c + 1, seen, h); dfs(r, c - 1, seen, h)
    pac, atl = set(), set()
    for c in range(C):
        dfs(0, c, pac, 0)
        dfs(R - 1, c, atl, 0)
    for r in range(R):
        dfs(r, 0, pac, 0)
        dfs(r, C - 1, atl, 0)
    return [[r, c] for r, c in (pac & atl)]
```

### TypeScript
```typescript
export function pacificAtlantic(heights: number[][]): number[][] {
  const R = heights.length, C = heights[0].length;
  const pac = new Set<number>(), atl = new Set<number>();
  const dfs = (r: number, c: number, seen: Set<number>, prevH: number) => {
    const key = r * C + c;
    if (r < 0 || r >= R || c < 0 || c >= C || seen.has(key) || heights[r][c] < prevH) return;
    seen.add(key);
    const h = heights[r][c];
    dfs(r + 1, c, seen, h); dfs(r - 1, c, seen, h);
    dfs(r, c + 1, seen, h); dfs(r, c - 1, seen, h);
  };
  for (let c = 0; c < C; c++) { dfs(0, c, pac, 0); dfs(R - 1, c, atl, 0); }
  for (let r = 0; r < R; r++) { dfs(r, 0, pac, 0); dfs(r, C - 1, atl, 0); }
  const res: number[][] = [];
  for (let r = 0; r < R; r++) {
    for (let c = 0; c < C; c++) {
      if (pac.has(r * C + c) && atl.has(r * C + c)) res.push([r, c]);
    }
  }
  return res;
}
```

### C++
```cpp
vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
    int R = h.size(), C = h[0].size();
    vector<vector<bool>> pac(R, vector<bool>(C)), atl(R, vector<bool>(C));
    auto dfs = [&](auto& self, int r, int c, vector<vector<bool>>& vis, int prev) -> void {
        if (r < 0 || r >= R || c < 0 || c >= C || vis[r][c] || h[r][c] < prev) return;
        vis[r][c] = true;
        self(self, r+1, c, vis, h[r][c]); self(self, r-1, c, vis, h[r][c]);
        self(self, r, c+1, vis, h[r][c]); self(self, r, c-1, vis, h[r][c]);
    };
    for (int c = 0; c < C; ++c) { dfs(dfs, 0, c, pac, 0); dfs(dfs, R-1, c, atl, 0); }
    for (int r = 0; r < R; ++r) { dfs(dfs, r, 0, pac, 0); dfs(dfs, r, C-1, atl, 0); }
    vector<vector<int>> res;
    for (int r = 0; r < R; ++r)
        for (int c = 0; c < C; ++c)
            if (pac[r][c] && atl[r][c]) res.push_back({r, c});
    return res;
}
```

### Java
```java
List<List<Integer>> pacificAtlantic(int[][] h) {
    int R = h.length, C = h[0].length;
    boolean[][] pac = new boolean[R][C], atl = new boolean[R][C];
    for (int c = 0; c < C; c++) { dfs(h, 0, c, pac, 0); dfs(h, R-1, c, atl, 0); }
    for (int r = 0; r < R; r++) { dfs(h, r, 0, pac, 0); dfs(h, r, C-1, atl, 0); }
    List<List<Integer>> res = new ArrayList<>();
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++)
            if (pac[r][c] && atl[r][c]) res.add(List.of(r, c));
    return res;
}
void dfs(int[][] h, int r, int c, boolean[][] vis, int prev) {
    if (r < 0 || r >= h.length || c < 0 || c >= h[0].length || vis[r][c] || h[r][c] < prev) return;
    vis[r][c] = true;
    dfs(h, r+1, c, vis, h[r][c]); dfs(h, r-1, c, vis, h[r][c]);
    dfs(h, r, c+1, vis, h[r][c]); dfs(h, r, c-1, vis, h[r][c]);
}
```

### Go
```go
func pacificAtlantic(h [][]int) [][]int {
    R, C := len(h), len(h[0])
    pac := make([][]bool, R); atl := make([][]bool, R)
    for i := range R { pac[i] = make([]bool, C); atl[i] = make([]bool, C) }
    var dfs func(int, int, [][]bool, int)
    dfs = func(r, c int, vis [][]bool, prev int) {
        if r < 0 || r >= R || c < 0 || c >= C || vis[r][c] || h[r][c] < prev { return }
        vis[r][c] = true
        dfs(r+1, c, vis, h[r][c]); dfs(r-1, c, vis, h[r][c])
        dfs(r, c+1, vis, h[r][c]); dfs(r, c-1, vis, h[r][c])
    }
    for c := 0; c < C; c++ { dfs(0, c, pac, 0); dfs(R-1, c, atl, 0) }
    for r := 0; r < R; r++ { dfs(r, 0, pac, 0); dfs(r, C-1, atl, 0) }
    var res [][]int
    for r := 0; r < R; r++ {
        for c := 0; c < C; c++ {
            if pac[r][c] && atl[r][c] { res = append(res, []int{r, c}) }
        }
    }
    return res
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Traversing downhill from every cell repeats work across shared valleys.
- Remember reverse flow uses `>=` (`heights[nr][nc] >= heights[r][c]`), not `<=`.

### Follow-ups
- Trapping Rain Water II generalizes perimeter inward elevation propagation with a min-heap.