Pacific Atlantic Water Flow

medium graph bfs matrix

Problem

An m×n grid of heights borders the Pacific Ocean (top + left edges) and the Atlantic Ocean (bottom + right edges). Water can flow from a cell to an adjacent cell that is the same height or lower. Return every cell from which water can reach both oceans.

Reverse the flow: start a search from each ocean's coastline and step only onto cells of equal or greater height. The intersection of the two reachable sets is the answer.

Input[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]

Output[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

heights (rows separated by ';')

def pacific_atlantic(h):
    m, n = len(h), len(h[0])
    pac, atl = set(), set()
    def dfs(r, c, seen):
        seen.add((r, c))
        for dr, dc in ((-1,0),(1,0),(0,-1),(0,1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen and h[nr][nc] >= h[r][c]:
                dfs(nr, nc, seen)
    for i in range(m): dfs(i, 0, pac); dfs(i, n - 1, atl)
    for j in range(n): dfs(0, j, pac); dfs(m - 1, j, atl)
    return [[r, c] for (r, c) in pac & atl]

function pacificAtlantic(h) {
  const m = h.length, n = h[0].length;
  const pac = new Set(), atl = new Set();
  const key = (r, c) => r * n + c;
  const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
  function dfs(r, c, seen) {
    seen.add(key(r, c));
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr>=0 && nr<m && nc>=0 && nc<n && !seen.has(key(nr,nc)) && h[nr][nc] >= h[r][c]) dfs(nr, nc, seen);
    }
  }
  for (let i = 0; i < m; i++) { dfs(i, 0, pac); dfs(i, n - 1, atl); }
  for (let j = 0; j < n; j++) { dfs(0, j, pac); dfs(m - 1, j, atl); }
  const res = [];
  for (const k of pac) if (atl.has(k)) res.push([Math.floor(k / n), k % n]);
  return res;
}

class Solution {
    int m, n; int[][] h;
    int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    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 i = 0; i < m; i++) { dfs(i, 0, pac); dfs(i, n - 1, atl); }
        for (int j = 0; j < n; j++) { dfs(0, j, pac); dfs(m - 1, j, atl); }
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
            if (pac[i][j] && atl[i][j]) res.add(Arrays.asList(i, j));
        return res;
    }
    void dfs(int r, int c, boolean[][] seen) {
        seen[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 && !seen[nr][nc] && h[nr][nc] >= h[r][c]) dfs(nr, nc, seen);
        }
    }
}

vector<vector<int>> pacificAtlantic(vector<vector<int>>& h) {
    int m = h.size(), n = h[0].size();
    vector<vector<int>> pac(m, vector<int>(n, 0)), atl(m, vector<int>(n, 0));
    vector<array<int,2>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    function<void(int,int,vector<vector<int>>&)> dfs = [&](int r, int c, auto& seen) {
        seen[r][c] = 1;
        for (auto& d : dirs) { int nr = r + d[0], nc = c + d[1];
            if (nr>=0 && nr<m && nc>=0 && nc<n && !seen[nr][nc] && h[nr][nc] >= h[r][c]) dfs(nr, nc, seen);
        }
    };
    for (int i = 0; i < m; i++) { dfs(i, 0, pac); dfs(i, n - 1, atl); }
    for (int j = 0; j < n; j++) { dfs(0, j, pac); dfs(m - 1, j, atl); }
    vector<vector<int>> res;
    for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (pac[i][j] && atl[i][j]) res.push_back({i, j});
    return res;
}

Explanation

The big idea is to reverse the flow. Instead of asking "can water from this cell reach the ocean?", we start at each ocean's coastline and flood inward, stepping only to cells that are the same height or higher. Any cell we can reach this way is a cell whose water could have flowed down to that ocean.

We do this flood twice: once from the Pacific coast (top row and left column) filling the set pac, and once from the Atlantic coast (bottom row and right column) filling atl. Each flood is a simple DFS that marks reachable cells.

The dfs(r, c, seen) marks the current cell, then moves to a neighbor only if it is in bounds, not yet seen, and h[nr][nc] >= h[r][c] (uphill or flat, since we are going against the real flow).

A cell that drains to both oceans must appear in both sets, so the answer is the intersection pac & atl.

Example: in the sample grid, flooding from each coast and intersecting yields cells like [0,4], [1,3], [2,2], [3,0], and [4,0] — exactly the cells touching both reachable regions.

Time: O(m·n) Space: O(m·n)