Pacific Atlantic Water Flow — DSA · Engineering Playbook

Problem#

In a heights grid, water flows to lower-or-equal cells. The Pacific borders the top and left edges; the Atlantic borders the bottom and right. Return all cells from which water can reach both oceans.

Examples#

[[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]] → cells including [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].

Constraints#

1 <= m, n <= 200.

Approach#

Reverse the flow: from each ocean’s border cells, BFS uphill to mark all cells whose water can flow into that ocean. Intersect the two reachability sets.

Solution#

class Solution {
public:
    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 = pac;
        int dr[4] = {-1, 1, 0, 0}, dc[4] = {0, 0, -1, 1};
        function<void(int,int,vector<vector<int>>&)> dfs = [&](int r, int c, vector<vector<int>>& vis) {
            vis[r][c] = 1;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k], nc = c + dc[k];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (vis[nr][nc] || h[nr][nc] < h[r][c]) continue;
                dfs(nr, nc, vis);
            }
        };
        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>> ans;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (pac[i][j] && atl[i][j]) ans.push_back({i, j});
        return ans;
    }
};

func pacificAtlantic(h [][]int) [][]int {
    m, n := len(h), len(h[0])
    pac := make([][]int, m)
    atl := make([][]int, m)
    for i := range pac {
        pac[i] = make([]int, n)
        atl[i] = make([]int, n)
    }
    dr := []int{-1, 1, 0, 0}
    dc := []int{0, 0, -1, 1}
    var dfs func(r, c int, vis [][]int)
    dfs = func(r, c int, vis [][]int) {
        vis[r][c] = 1
        for k := 0; k < 4; k++ {
            nr, nc := r+dr[k], c+dc[k]
            if nr < 0 || nr >= m || nc < 0 || nc >= n {
                continue
            }
            if vis[nr][nc] == 1 || h[nr][nc] < h[r][c] {
                continue
            }
            dfs(nr, nc, vis)
        }
    }
    for i := 0; i < m; i++ {
        dfs(i, 0, pac)
        dfs(i, n-1, atl)
    }
    for j := 0; j < n; j++ {
        dfs(0, j, pac)
        dfs(m-1, j, atl)
    }
    var ans [][]int
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pac[i][j] == 1 && atl[i][j] == 1 {
                ans = append(ans, []int{i, j})
            }
        }
    }
    return ans
}

from typing import List

class Solution:
    def pacificAtlantic(self, h: List[List[int]]) -> List[List[int]]:
        m, n = len(h), len(h[0])
        pac = [[0] * n for _ in range(m)]
        atl = [[0] * n for _ in range(m)]
        dr = (-1, 1, 0, 0)
        dc = (0, 0, -1, 1)

        def dfs(r: int, c: int, vis: List[List[int]]) -> None:
            vis[r][c] = 1
            for k in range(4):
                nr, nc = r + dr[k], c + dc[k]
                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue
                if vis[nr][nc] or h[nr][nc] < h[r][c]:
                    continue
                dfs(nr, nc, vis)

        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)

        ans: List[List[int]] = []
        for i in range(m):
            for j in range(n):
                if pac[i][j] and atl[i][j]:
                    ans.append([i, j])
        return ans

function pacificAtlantic(h) {
    const m = h.length, n = h[0].length;
    const pac = Array.from({ length: m }, () => new Array(n).fill(0));
    const atl = Array.from({ length: m }, () => new Array(n).fill(0));
    const dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1];
    const dfs = (r, c, vis) => {
        vis[r][c] = 1;
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (vis[nr][nc] || h[nr][nc] < h[r][c]) continue;
            dfs(nr, nc, vis);
        }
    };
    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 ans = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pac[i][j] && atl[i][j]) ans.push([i, j]);
        }
    }
    return ans;
}

class Solution {
    private int m, n;
    private int[][] h;
    private int[] dr = {-1, 1, 0, 0};
    private int[] dc = {0, 0, -1, 1};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        h = heights;
        m = h.length;
        n = h[0].length;
        int[][] pac = new int[m][n];
        int[][] atl = new int[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>> ans = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pac[i][j] == 1 && atl[i][j] == 1) {
                    ans.add(Arrays.asList(i, j));
                }
            }
        }
        return ans;
    }

    private void dfs(int r, int c, int[][] vis) {
        vis[r][c] = 1;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (vis[nr][nc] == 1 || h[nr][nc] < h[r][c]) continue;
            dfs(nr, nc, vis);
        }
    }
}

function pacificAtlantic(h: number[][]): number[][] {
    const m = h.length, n = h[0].length;
    const pac: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
    const atl: number[][] = Array.from({ length: m }, () => new Array(n).fill(0));
    const dr: number[] = [-1, 1, 0, 0], dc: number[] = [0, 0, -1, 1];
    const dfs = (r: number, c: number, vis: number[][]): void => {
        vis[r][c] = 1;
        for (let k = 0; k < 4; k++) {
            const nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
            if (vis[nr][nc] || h[nr][nc] < h[r][c]) continue;
            dfs(nr, nc, vis);
        }
    };
    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 ans: number[][] = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pac[i][j] && atl[i][j]) ans.push([i, j]);
        }
    }
    return ans;
}

Editorial#

The reverse-flow trick is the key — starting at the oceans and walking uphill is symmetric to “can this cell flow to the ocean?” and avoids re-running BFS per cell. Each cell is visited at most twice.

Complexity#

Time: O(m * n).
Space: O(m * n).

Concept revision#

Number of Islands