Pacific Atlantic Water Flow

Medium Graphs Multi source BFS Original on LeetCode

Pacific Atlantic Water Flow is a medium graphs problem solved with the multi source bfs pattern. The best approach, optimal (reverse bfs from both oceans), runs in O(m · n) time and O(m · n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (search from every cell) up.

Problem

An island is described by an m x n grid heights, where heights[r][c] is the height of land at row r and column c. The Pacific Ocean borders the top and left edges of the island, and the Atlantic Ocean borders the bottom and right edges.

Rain on a cell can flow to any of its four neighbours whose height is less than or equal to its own, and from any cell on the border straight into the ocean next to that edge.

Return the coordinates [r, c] of every cell from which rain water can reach both oceans, in any order.

Examples

Example 1

Input
heights = [[3,3,4],[2,5,1],[6,1,2]]
Output
[[0,2],[1,1],[2,0]]
Why
From 5 water can run north onto the 3 (then into the Pacific) or east onto the 1 (then into the Atlantic). The two corners [0,2] and [2,0] touch both oceans directly.

Example 2

Input
heights = [[7]]
Output
[[0,0]]
Why
A single cell borders all four sides, so it drains into both oceans.

Example 3

Input
heights = [[1,2],[2,1]]
Output
[[0,1],[1,0]]
Why
The two 2s are corners touching both oceans. Each 1 is a low point touching only one ocean.

Constraints

  • 1 <= m, n <= 200 where m and n are the number of rows and columns.
  • 0 <= heights[i][j] <= 10^5
  • The answer may be returned in any order.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (search from every cell)O((m · n)²)O(m · n)
Optimal (reverse BFS from both oceans)O(m · n)O(m · n)

1Brute force (search from every cell)

TimeO((m · n)²)Each of the m · n searches can visit the whole grid.
SpaceO(m · n)The visited array and queue of one search.

For each cell, run a BFS that follows water downhill (to neighbours of equal or lower height). Record whether the search reaches a Pacific border cell (row 0 or column 0) and an Atlantic border cell (last row or last column).

  1. For each cell (i, j): BFS over neighbours with height <= current height.
  2. Set pac when a visited cell has r == 0 or c == 0; set atl when r == m - 1 or c == n - 1.
  3. If both are set, add [i, j] to the answer.
class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                boolean[][] seen = new boolean[m][n];
                ArrayDeque<int[]> q = new ArrayDeque<>();
                q.add(new int[] { i, j });
                seen[i][j] = true;
                boolean pac = false, atl = false;
                while (!q.isEmpty() && !(pac && atl)) {
                    int[] c = q.poll();
                    if (c[0] == 0 || c[1] == 0) pac = true;
                    if (c[0] == m - 1 || c[1] == n - 1) atl = true;
                    for (int[] d : dirs) {
                        int x = c[0] + d[0], y = c[1] + d[1];
                        if (x >= 0 && y >= 0 && x < m && y < n && !seen[x][y]
                                && heights[x][y] <= heights[c[0]][c[1]]) {
                            seen[x][y] = true;
                            q.add(new int[] { x, y });
                        }
                    }
                }
                if (pac && atl) ans.add(Arrays.asList(i, j));
            }
        return ans;
    }
}

2Optimal (reverse BFS from both oceans)

TimeO(m · n)Each BFS visits every cell at most once and checks 4 neighbours.
SpaceO(m · n)Two visited grids and the BFS queue.

Run the flow backwards. A multi-source BFS starting from every Pacific border cell, moving only to neighbours that are at least as high, finds exactly the cells whose water can reach the Pacific. A second BFS from the Atlantic border does the same for the Atlantic. Return the cells marked by both.

  1. pac = BFS seeded with row 0 and column 0; atl = BFS seeded with row m - 1 and column n - 1.
  2. In each BFS, move from (r, c) to a neighbour (x, y) when it is unvisited and heights[x][y] >= heights[r][c].
  3. Scan the grid and collect [i, j] where pac[i][j] and atl[i][j] are both true.
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;
        ArrayDeque<int[]> pq = new ArrayDeque<>(), aq = new ArrayDeque<>();
        boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            seed(pq, pac, i, 0);
            seed(aq, atl, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            seed(pq, pac, 0, j);
            seed(aq, atl, m - 1, j);
        }
        bfs(heights, pq, pac);
        bfs(heights, aq, 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] && atl[i][j]) ans.add(Arrays.asList(i, j));
        return ans;
    }

    private void seed(ArrayDeque<int[]> q, boolean[][] seen, int r, int c) {
        if (!seen[r][c]) {
            seen[r][c] = true;
            q.add(new int[] { r, c });
        }
    }

    private void bfs(int[][] h, ArrayDeque<int[]> q, boolean[][] seen) {
        int m = h.length, n = h[0].length;
        while (!q.isEmpty()) {
            int[] c = q.poll();
            for (int[] d : DIRS) {
                int x = c[0] + d[0], y = c[1] + d[1];
                if (x >= 0 && y >= 0 && x < m && y < n && !seen[x][y] && h[x][y] >= h[c[0]][c[1]]) {
                    seen[x][y] = true;
                    q.add(new int[] { x, y });
                }
            }
        }
    }
}

Edge cases to test

  • A single row or a single column (every cell touches both oceans)
  • All heights equal (every cell qualifies)
  • Water can flow across equal heights, not just strictly downhill
  • A deep basin in the middle that can reach neither ocean

Hints

Hint 1

Checking every cell separately means one search per cell. Can you flip the question around?

Hint 2

Instead of asking where water from a cell goes, ask which cells can drain into the Pacific. Start from the Pacific border and walk uphill (to neighbours of equal or greater height).

Hint 3

Do the same from the Atlantic border. The cells reached by both searches are the answer.

FAQ

What is the best time complexity for Pacific Atlantic Water Flow?

Optimal (reverse BFS from both oceans) runs in O(m · n) time and O(m · n) extra space. Each BFS visits every cell at most once and checks 4 neighbours.

Which pattern does Pacific Atlantic Water Flow use?

It is a graphs problem that uses the multi source bfs pattern. Other problems with the same pattern: Rotting Oranges, 01 Matrix, Escape the Spreading Fire.

Is there a brute force solution for Pacific Atlantic Water Flow?

Yes. Brute force (search from every cell) takes O((m · n)²) time and O(m · n) space. For each cell, run a BFS that follows water downhill (to neighbours of equal or lower height).

Which edge cases should I test for Pacific Atlantic Water Flow?

A single row or a single column (every cell touches both oceans); All heights equal (every cell qualifies); Water can flow across equal heights, not just strictly downhill; A deep basin in the middle that can reach neither ocean.