mediumGraphs

Pacific Atlantic Water Flow

The top and left edges of a height grid touch one ocean; the bottom and right edges touch another. Water flows to adjacent cells of equal or lower height. Find cells from which water can reach both oceans.

LeetCode ↗

Work through the cases

3 examples

Input notation

Rows of a nonempty rectangular matrix, one space-separated row per line.

Expected result

Zero-based row column pairs, sorted by row then column, one per line.

Case 1

Input

1 2
4 3

Expected output

0 1
1 0
1 1

Case 2

Input

Expected output

0 0

Case 3

Input

1 1
1 1

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Walking downhill from every cell toward an ocean revisits the same cells. With m,n ≤ 200 that duplication is costly. The reverse of flowing down is climbing to a neighbor that is at least as high. BFS from the Pacific border and from the Atlantic border; the intersection can reach both oceans. A neighbor is admissible only when heights[nx][ny] ≥ heights[x][y]. Starting at a border guarantees a path back to that ocean.

We can start from the boundaries of the Pacific and Atlantic oceans and perform breadth-first search (BFS) respectively to find all cells that can flow to the Pacific and Atlantic oceans. Finally, we take the intersection of the two results, which represents cells that can flow to both the Pacific and Atlantic oceans.

Specifically, we define a queue q_1 to store all cells adjacent to the Pacific ocean, and define a boolean matrix vis_1 to record which cells can flow to the Pacific ocean. Similarly, we define queue q_2 and boolean matrix vis_2 to handle the Atlantic ocean. Initially, we add all cells adjacent to the Pacific ocean to queue q_1 and mark them as visited in vis_1. Similarly, we add all cells adjacent to the Atlantic ocean to queue q_2 and mark them as visited in vis_2.

Then, we perform BFS on q_1 and q_2 respectively. In each BFS, we dequeue a cell (x, y) from the queue and check its four adjacent cells (nx, ny). If an adjacent cell is within the matrix bounds, has not been visited, and its height is not less than the current cell's height (i.e., water can flow to that cell), we add it to the queue and mark it as visited.

Finally, we traverse the entire matrix to find cells that are marked as visited in both vis_1 and vis_2. These cells are our answer.

The time complexity is O(m × n) and the space complexity is O(m × n), where m and n are the number of rows and columns in the matrix, respectively.

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] vis1 = new boolean[m][n];
        boolean[][] vis2 = new boolean[m][n];
        Deque<int[]> q1 = new ArrayDeque<>();
        Deque<int[]> q2 = new ArrayDeque<>();
        int[] dirs = {-1, 0, 1, 0, -1};

        for (int i = 0; i < m; ++i) {
            q1.offer(new int[] {i, 0});
            vis1[i][0] = true;
            q2.offer(new int[] {i, n - 1});
            vis2[i][n - 1] = true;
        }
        for (int j = 0; j < n; ++j) {
            q1.offer(new int[] {0, j});
            vis1[0][j] = true;
            q2.offer(new int[] {m - 1, j});
            vis2[m - 1][j] = true;
        }

        BiConsumer<Deque<int[]>, boolean[][]> bfs = (q, vis) -> {
            while (!q.isEmpty()) {
                var cell = q.poll();
                int x = cell[0], y = cell[1];
                for (int k = 0; k < 4; ++k) {
                    int nx = x + dirs[k], ny = y + dirs[k + 1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !vis[nx][ny]
                        && heights[nx][ny] >= heights[x][y]) {
                        vis[nx][ny] = true;
                        q.offer(new int[] {nx, ny});
                    }
                }
            }
        };

        bfs.accept(q1, vis1);
        bfs.accept(q2, vis2);

        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (vis1[i][j] && vis2[i][j]) {
                    ans.add(List.of(i, j));
                }
            }
        }
        return ans;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.