Pacific Atlantic Water Flow

The problem

An island is drawn as a grid heights with m rows and n columns, where each number is the height of that patch of land. The Pacific ocean lies past the top and left edges. The Atlantic lies past the bottom and right edges.

Rain on a cell flows to any of its four neighbors (up, down, left, right) that is not higher than the cell. A cell on an edge also drains straight into the ocean on that side. Return every cell [row, column] from which rain can reach both oceans, in any order.

Example 1

Input: heights = [[1, 2, 3], [2, 5, 4], [3, 4, 2]]

Output: [[0, 2], [1, 1], [1, 2], [2, 0], [2, 1]]

The 5 in the middle can flow down to every cell. The 1 in the corner reaches only the Pacific: every neighbor is higher. The 2 in the bottom right corner reaches only the Atlantic.

	0	1	2
0	1	2	3
1	2	5	4
2	3	4	2

Example 2

Input: heights = [[4]]

Output: [[0, 0]]

One cell touches all four edges, so it drains into both oceans.

Example 3

Input: heights = [[1, 2], [4, 3]]

Output: [[0, 1], [1, 0], [1, 1]]

The 1 at the top left touches only the Pacific edges, and both its neighbors are higher.

Constraints

• 1 ≤ m, n ≤ 200
• 0 ≤ heights[row][column] ≤ 100,000

Clarifying questions

Can water flow between cells of the same height?

Yes. It moves to any neighbor that is not higher, so equal heights pass water both ways.

Which edges belong to which ocean?

Top and left are the Pacific. Bottom and right are the Atlantic. The top right and bottom left corners touch both.

Does water move diagonally?

No. Only up, down, left and right.

Does the order of the answer matter?

No. Any order is fine.

Spot the pattern

Cells are nodes, and water can move from one cell to a neighbor: those moves are edges. “Which cells can reach the ocean?” is a question about reachability in a graph, so it is graph search. The twist is to search in the other direction. Asking “which cells can reach this ocean?” from the ocean’s side needs one search per ocean, not one search per cell.

Solutions

Search from every cellO((m × n)²)Flood from the oceansO(m × n)

Show all

There is no middle approach worth its own tab. Saving the answer for each cell to reuse it fails, because water can flow back and forth between cells of the same height, so the results depend on each other in a loop.

Search from every cell O((m × n)²)

The idea

Do what the problem says. For every cell, run a search that follows the water: from a cell, step to any neighbor that is not higher, and mark every cell reached. If any reached cell is on the top or left edge, the water gets to the Pacific. If any is on the bottom or right edge, it gets to the Atlantic. Keep the start cell if both are true.

Why it is correct: the search finds every cell the rain can flow to, so it sees an edge exactly when the rain can drain off it.

Walkthrough

	0	1	2
0	1	2	3
1	2	5	4
2	3	4	2

answer

empty

1. for each cell (row, column):
2. search from (row, column), moving to neighbors that are not higher
3. pacific = the search touched the top or left edge
4. atlantic = the search touched the bottom or right edge
5. if pacific and atlantic: answer.add([row, column])
6. return answer

Water flows from a cell to a neighbor that is not higher. The Pacific is past the top and left edges, the Atlantic past the bottom and right edges. Try every cell as the start.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private int[][] heights;
    private int rows, columns;

    // Brute force: from every cell, follow the water downhill and see which
    // oceans it reaches. Each search can cover the whole grid again.
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        rows = heights.length;
        columns = heights[0].length;
        List<List<Integer>> result = new ArrayList<>();
        for (int row = 0; row < rows; row++)
            for (int column = 0; column < columns; column++)
                if (reachesBoth(row, column)) result.add(List.of(row, column));
        return result;
    }

    private boolean reachesBoth(int startRow, int startColumn) {
        boolean pacific = false, atlantic = false;
        boolean[][] seen = new boolean[rows][columns];
        Deque<int[]> stack = new ArrayDeque<>();
        seen[startRow][startColumn] = true;
        stack.push(new int[] { startRow, startColumn });
        int[][] directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            int row = cell[0], column = cell[1];
            // Touching the top or left edge means the water can spill into the Pacific.
            if (row == 0 || column == 0) pacific = true;
            if (row == rows - 1 || column == columns - 1) atlantic = true;
            for (int[] direction : directions) {
                int nextRow = row + direction[0], nextColumn = column + direction[1];
                // Water moves only to a cell that is not higher.
                if (nextRow >= 0 && nextRow < rows && nextColumn >= 0 && nextColumn < columns
                    && !seen[nextRow][nextColumn]
                    && heights[nextRow][nextColumn] <= heights[row][column]) {
                    seen[nextRow][nextColumn] = true;
                    stack.push(new int[] { nextRow, nextColumn });
                }
            }
        }
        return pacific && atlantic;
    }
}

Big O

Time O((m × n)²)Space O(m × n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The outer loop runs once per cell. Inside it, a whole search runs. A search takes one cell off its stack at a time and checks its 4 neighbors, a fixed job. So we count the cells each search reaches: each one is 1 step.

   1. for each cell (row, column):
   2. search from (row, column), moving to neighbors that are not higher
   3. pacific = the search touched the top or left edge
   4. atlantic = the search touched the bottom or right edge
   5. if pacific and atlantic: answer.add([row, column])
   6. return answer

2. 2 Count the runs on Example 1

   The table is laid out like the grid. Each number is how many cells the search from that cell reached. The 5 in the middle is the highest cell, so its search reached all 9.

   1 + 2 + 3 + 2 + 9 + 5 + 3 + 5 + 1 = 31 steps.

   	0	1	2
   0	1	2	3
   1	2	9	5
   2	3	5	1

   cells searched, all starts

   1 + 2 + 3 + 2 + 9 + 5 + 3 + 5 + 1 = 31

3. 3 Write the count for any n

   There are m × n starts, and one search can reach every cell: m × n steps.

   m × n × m × n = (m × n)² steps

   Check it with Example 1: the bound is 9 × 9 = 81. The real run used 31, because most cells are low and reach only a few others. A grid that is all one height reaches the bound.

4. 4 Keep only the part that grows fastest

   Nothing to drop. (m × n)² grows fast: a 200 × 200 grid has 40,000 cells, so the worst case is 1.6 billion steps. Too slow.

   So the time is O((m × n)²).

5. S Space: count the extra memory the same way

   Each search keeps a seen set and a stack, each up to m × n cells. They are thrown away before the next search, so the space is O(m × n).

   seen set (up to m × n)search stack (up to m × n)

Flood from the oceans O(m × n)

The idea

The brute force searches again from every cell, and most of that work repeats. Turn it around: start at the ocean and ask which cells could have sent water to it.

Water flows from high to low, so going backwards it climbs. Start a flood at every cell on the Pacific edges. From a cell, step to a neighbor that is the same height or higher, and mark it. Every marked cell can drain into the Pacific. Do the same from the Atlantic edges with a second set. The answer is every cell in both sets.

Each flood keeps its own stack of marked cells whose neighbors are not checked yet. We do not use recursion: one climbing path can snake through the whole grid, 40,000 cells, and a recursive flood that deep overflows the call stack (the memory a program keeps for calls that have not returned yet).

Why it is correct: water can go from cell A down to the ocean edge exactly when the reversed path climbs from that edge up to A. The flood follows every climbing path, so it marks exactly the cells that drain into that ocean.

Walkthrough

	0	1	2
0	1	2	3
1	2	5	4
2	3	4	2

stack top →

empty

pacific

0

atlantic

0

1. pacific, atlantic = set(), set()
2. for each cell on the top or left edge:
3. flood(row, column, pacific)
4. for each cell on the bottom or right edge:
5. flood(row, column, atlantic)
6. return cells in both pacific and atlantic
7. def flood(start_row, start_column, seen):
8. seen.add(start); stack = [start]
9. while stack:
10. row, column = stack.pop()
11. for each neighbor not in seen and not lower:
12. seen.add(neighbor); stack.append(neighbor)

Turn the question around. Start at each ocean and walk uphill: to a neighbor that is the same height or higher. Any cell we reach could send water down to that ocean.

← BackStep →Play1 / 24

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    private int[][] heights;
    private int rows, columns;

    // Reverse flood: start at each ocean's edge and climb uphill. A cell that
    // both floods reach can drain to both oceans. Each flood visits a cell once.
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        rows = heights.length;
        columns = heights[0].length;
        boolean[][] pacific = new boolean[rows][columns], atlantic = new boolean[rows][columns];
        for (int row = 0; row < rows; row++) {
            flood(row, 0, pacific);
            flood(row, columns - 1, atlantic);
        }
        for (int column = 0; column < columns; column++) {
            flood(0, column, pacific);
            flood(rows - 1, column, atlantic);
        }
        List<List<Integer>> result = new ArrayList<>();
        for (int row = 0; row < rows; row++)
            for (int column = 0; column < columns; column++)
                if (pacific[row][column] && atlantic[row][column]) result.add(List.of(row, column));
        return result;
    }

    private void flood(int startRow, int startColumn, boolean[][] seen) {
        // Our own stack instead of recursion: a recursive flood can go as deep as the grid
        // has cells (40,000), which overflows the call stack.
        // Mark a cell as it goes on the stack, so no cell is pushed twice.
        seen[startRow][startColumn] = true;
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[] { startRow, startColumn });
        int[][] directions = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            int row = cell[0], column = cell[1];
            for (int[] direction : directions) {
                int neighborRow = row + direction[0], neighborColumn = column + direction[1];
                // Going backwards, water came from a cell that is not lower.
                if (neighborRow >= 0 && neighborRow < rows && neighborColumn >= 0 && neighborColumn < columns
                    && !seen[neighborRow][neighborColumn]
                    && heights[neighborRow][neighborColumn] >= heights[row][column]) {
                    seen[neighborRow][neighborColumn] = true;
                    stack.push(new int[] { neighborRow, neighborColumn });
                }
            }
        }
    }
}

Big O

Time O(m × n)Space O(m × n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The work repeats in the while loop of flood, so we count the pops from the stack. A pop takes one cell and checks its 4 neighbors: a fixed job, so 1 step. The final loop that collects the answer runs once per cell.

   1. pacific, atlantic = set(), set()
   2. for each cell on the top or left edge:
   3. flood(row, column, pacific)
   4. for each cell on the bottom or right edge:
   5. flood(row, column, atlantic)
   6. return cells in both pacific and atlantic
   7. def flood(start_row, start_column, seen):
   8. seen.add(start); stack = [start]
   9. while stack:
   10. row, column = stack.pop()
   11. for each neighbor not in seen and not lower:
   12. seen.add(neighbor); stack.append(neighbor)

2. 2 Count the runs on Example 1

   Each flood starts once from every edge cell on its side: 3 + 3 = 6 starts. Some starts land on a cell the same flood already marked: that cell is popped once more and adds nothing. Every other pop is a cell marked for the first time.

   13 + 9 = 22 pops, marking 8 + 6 = 14 cells.

   	Pacific flood	Atlantic flood
   pops	13	9
   cells marked	8	6

   total pops

   13 + 9 = 22

3. 3 Write the count for any n

   A flood pushes a neighbor only if that neighbor is not marked yet, and marks it as it pushes. So it pops each cell at most once, plus once more for each of the m + n starts from the edges. With two floods:

   2 × (m × n + m + n) pops, plus m × n for the answer loop

   Check it with Example 1: 2 × (9 + 3 + 3) = 30 pops at most. The real run made 22.

4. 4 Keep only the part that grows fastest

   m + n is never more than m × n + 1, so drop the m + n and the constants. What is left is m × n: the size of the grid, once per ocean instead of once per cell.

   So the time is O(m × n).

5. S Space: count the extra memory the same way

   The two sets hold up to m × n cells each. The flood’s stack holds each cell at most once, so it never holds more than m × n cells. So the space is O(m × n).

   pacific set (m × n)atlantic set (m × n)flood stack (up to m × n)

Common mistake

Climbing with the wrong comparison

Going backwards, the next cell must be at least as high, so >=. Writing > loses cells of equal height, which water can cross. Writing <= floods downhill, which answers a different question.

Tested at the limits

2,000 random grids of up to 5 x 5 cells with heights 0 to 3, so flat areas of equal height come up a lot. The search from every cell and the flood from the oceans found the same cells every time.

Largest inputs	Result
A flat 200 x 200 grid (the most allowed). Every cell drains to both oceans, so each flood covers all 40,000 cells. Flood from the oceans.	0.09 s, and about 11 MB of extra memory: two seen sets of 40,000 cells each, plus the answer of 40,000 cells.
A random 200 x 200 grid, heights up to 100,000. Flood from the oceans.	Under 0.01 s, and about 0.07 MB of extra memory: on rough ground each flood stops close to its own coast.
A 25 x 25 corner of the random grid. Search from every cell.	0.005 s, with the same cells as the flood. At 200 x 200 it would run 40,000 searches, and on a flat grid each one covers all 40,000 cells: 1.6 billion steps.