Start learning free

LESSON 478 OF 536 · GRAPHS

Pacific Atlantic Water Flow in Java: Two BFS Searches in O(m · n)

Practice O(m · n) Read the full explanation

A rectangular island lies between two oceans. The Pacific Ocean touches its left and top edges, and the Atlantic Ocean touches its right and bottom edges.

The island is a grid of square cells with m rows and n columns, given as heights: an array of rows, where each row is an array of integers and heights[r][c] is the height of the cell in row r and column c. Rows are numbered from 0, top to bottom, and columns from 0, left to right.

Rain falls on every cell. Water flows from a cell to a neighboring cell (up, down, left or right) when the neighbor's height is less than or equal to the cell's height, and from any cell on an edge into the ocean that touches that edge.

Return the cells from which water can flow to both oceans, as an ArrayList of [r, c] pairs, in reading order: row by row from the top, and left to right within a row.

 

Example 1:

Input: heights = [
  [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]]
Explanation: [0, 4] is on the top edge (Pacific) and on the right edge (Atlantic).
From [2, 2], height 5, water runs up to the Pacific through [1, 2] and [0, 2] (heights 3 and 2),
and right to the Atlantic through [2, 3] and [2, 4] (heights 3 and 1).
From [3, 1], height 7, it runs left to [3, 0] (height 6, on the Pacific's edge) and down to [4, 1]
(height 1, on the Atlantic's edge).
[2, 1], height 4, reaches the Pacific through [2, 0], but every path to the Atlantic needs a step up.

Example 2:

Input: heights = [[1]]
Output: [[0, 0]]
Explanation: The only cell touches all four edges, so its water reaches both oceans.

Example 3:

Input: heights = [
  [5, 5, 5],
  [5, 1, 5],
  [5, 5, 5]
]
Output: [[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]]
Explanation: Water flows between cells of equal height, so the 5s pass it along the border
to both oceans. The 1 in the middle is lower than all its neighbors: its water stays where it is.

 

Constraints:

  • 1 <= m, n <= 200
  • Every row has n values.
  • 0 <= heights[r][c] <= 105

Note:

Your algorithm should run in O(m · n) time and use O(m · n) extra space.

Following the water down from every cell, one search per cell, can cost O((m · n)2): think of a large flat lake in the middle of the island, where each cell's search wanders over the whole lake before it gives up. The tutorial turns the question around and climbs up from the oceans instead. A BFS starts from all the cells along the Pacific's edges at once, as the BFS in 01 Matrix starts from all the zeros, and moves to a neighbor only when the neighbor is at least as high, because water from there could flow down to here. Every cell it reaches can send its water to the Pacific. A second BFS does the same from the Atlantic's edges, and the answer is the cells that both searches reach. Each search visits every cell at most once.

STEP 1 OF 26
    Ctrl + Enter to check

    JAVA · GRAPHS

    Pacific Atlantic Water Flow in Java, explained

    Problem overview

    A rectangular island lies between two oceans. The Pacific touches its left and top edges, and the Atlantic touches its right and bottom edges. The island is the grid heights with m rows and n columns, and heights[r][c] is the height of the cell in row r and column c. Water flows from a cell to a neighbour (up, down, left or right) whose height is less than or equal to the cell's, and from any cell on an edge into the ocean that touches that edge.

    The method pacificAtlantic returns the cells from which water can reach both oceans, as a List<List<Integer>> of [r, c] pairs in reading order: row by row from the top, left to right within a row.

    For the 5 by 5 grid in the first example, the answer is [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]. The cell [0, 4] is on the top edge and on the right edge, so it touches both oceans. For [[1]] the answer is [[0, 0]], since the only cell touches all four edges. For the grid of 5s around a single 1, the answer is every cell except the middle one: water moves between equal heights, so the border passes it along to both oceans, while the 1 is lower than all its neighbours and its water stays put.

    The statement asks for O(m · n) time and O(m · n) extra space, with grids up to 200 by 200.

    Approach: climb up from each ocean

    The obvious way is to follow the water downhill from every cell, one search per cell. That can cost O((m · n)²): picture a large flat lake in the middle, where each cell's search wanders over the whole lake before giving up.

    The better idea turns the question around. Start from the ocean and walk against the flow. A breadth-first search begins at every cell along the Pacific's two edges at once and moves to a neighbour only when the neighbour is at least as high, because water from that neighbour can flow down into the current cell and onward to the ocean. Every cell the search reaches can send its water to the Pacific. A second search does the same from the Atlantic's edges. The answer is the set of cells that both searches reach, listed in reading order.

    Each search visits each cell at most once, so two searches plus one pass over the grid are linear in the number of cells. For the first example, the cells marked 1 below are those the Pacific search reaches, then those the Atlantic search reaches:

    pacific   atlantic
11111     00001
11111     00011
11100     00111
11000     11111
10000     11111

    The cells marked in both grids are exactly the seven listed in the answer. The cell [2, 1], height 4, is marked for the Pacific only: it reaches the Pacific through [2, 0], but every path to the Atlantic needs a step up.

    Step by step

    1. Store the grid size in rows (heights.length) and cols (heights[0].length). Every row has the same length.
    2. Find the Pacific cells with reach(heights, 0, 0), stored in pacific. The helper is written afterwards. It takes an edge row and an edge column and marks every cell whose water can flow to them. The Pacific touches row 0 and column 0.
    3. Find the Atlantic cells with reach(heights, rows - 1, cols - 1), stored in atlantic. One helper serves both oceans, and only the edges differ.
    4. Create result, a List<List<Integer>> backed by an ArrayList.
    5. Loop over the rows with r. Going row by row, and left to right within a row, produces the required order.
    6. Loop over the columns with c.
    7. Add the cell as Arrays.asList(r, c) when both pacific[r][c] and atlantic[r][c] are true.
    8. Return result.
    9. Write reach, taking heights, edgeRow and edgeCol and returning a boolean[][]. It climbs up from the ocean with a BFS that only moves to cells at least as high.
    10. Store rows and cols again. The variables of pacificAtlantic aren't visible inside the helper.
    11. Create seen, a boolean[rows][cols] that starts all false. A cell becomes true once the search has reached it.
    12. Create queue, a Deque<int[]> backed by an ArrayDeque. Each element is a cell, an int[] holding its row and column.
    13. Loop over the rows to seed the search from the whole ocean border at once.
    14. Loop over the columns.
    15. Test r == edgeRow || c == edgeCol: a cell on the edge row or the edge column touches the ocean.
    16. Mark and queue it: set seen[r][c] to true and add new int[]{r, c} to the queue. Marking at the moment of queueing ensures no cell is queued twice.
    17. Define directions, the four moves as row and column changes. Each move changes only one of them, so diagonal cells aren't neighbours.
    18. Loop while the queue isn't empty.
    19. Take the front cell with poll into cell.
    20. Copy its values into row and col, which read better than cell[0] and cell[1].
    21. Loop over directions with an enhanced for.
    22. Compute the neighbour: nextRow is row + d[0] and nextCol is col + d[1].
    23. Check that it is inside the grid before using it as an index.
    24. Check that the search can climb to it: it isn't seen yet and its height is at least the current cell's. This is the key line: the search walks against the flow.
    25. Mark and queue the neighbour. Its water reaches this ocean too, and its own neighbours are checked when it leaves the queue.
    26. Return seen after the loop. A true entry means the cell's water reaches this ocean.

    The solution in Java

    class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int rows = heights.length;
        int cols = heights[0].length;
        boolean[][] pacific = reach(heights, 0, 0);
        boolean[][] atlantic = reach(heights, rows - 1, cols - 1);
        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.add(Arrays.asList(r, c));
                }
            }
        }
        return result;
    }

    boolean[][] reach(int[][] heights, int edgeRow, int edgeCol) {
        int rows = heights.length;
        int cols = heights[0].length;
        boolean[][] seen = new boolean[rows][cols];
        Deque<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == edgeRow || c == edgeCol) {
                    seen[r][c] = true;
                    queue.add(new int[]{r, c});
                }
            }
        }
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0];
            int col = cell[1];
            for (int[] d : directions) {
                int nextRow = row + d[0];
                int nextCol = col + d[1];
                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
                    if (!seen[nextRow][nextCol] && heights[nextRow][nextCol] >= heights[row][col]) {
                        seen[nextRow][nextCol] = true;
                        queue.add(new int[]{nextRow, nextCol});
                    }
                }
            }
        }
        return seen;
    }
}

    The Java details worth a closer look:

    • Two-dimensional arrays. new boolean[rows][cols] creates rows arrays of cols booleans, all false. heights[0].length is the width because each row is its own array.
    • Cells as int[]. The queue holds small arrays of two integers. That avoids writing a class for a cell, at the price of reading cell[0] and cell[1].
    • Arrays.asList(r, c) builds a list from its arguments. The int values are boxed to Integer, and the result is a fixed-size list, which is fine for a pair that is never changed. The lesson's editor already provides java.util. In a file of your own, add import java.util.*;.
    • Array initializer. int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; is allowed in a declaration and lets the four neighbours be handled by one loop.
    • Bounds check first. The check of nextRow and nextCol sits in its own if, around the one that reads seen and heights. Skipping it would throw an ArrayIndexOutOfBoundsException at the edges.
    • Helper results. reach returns the seen array itself, which the caller then reads. Arrays are objects, so this returns a reference and copies nothing.

    Complexity

    Each call of reach queues every cell at most once, because a cell is marked when it joins the queue. For each queued cell it looks at 4 neighbours, so one search is O(m · n). Two searches and the final pass over the grid keep the total at O(m · n). The two seen grids, the queue and the result use O(m · n) extra space.

    Edge cases and common mistakes

    • Using > instead of >=. Water also flows between cells of equal height, and the search must climb to equal cells. With a strict comparison, the grid of 5s around the 1 would lose cells such as [1, 2], which reaches the Pacific only through its equal neighbour [0, 2].
    • Climbing the wrong way. The search moves to neighbours that are at least as high, not lower ones. Following the water downhill from the ocean's edge gives the wrong set.
    • A single row. Every cell is on both the top and the bottom edge, so all of them reach both oceans. In [[1, 2, 3]] all three cells are returned.
    • Marking cells late. Marking a cell when it leaves the queue, not when it joins, can queue the same cell many times.
    • Mixing up row and column in the edge test. The condition r == edgeRow || c == edgeCol covers a whole row and a whole column. For the Pacific those are row 0 and column 0, and for the Atlantic they are the last row and the last column.
    • Pits. A cell lower than all its neighbours, like the 1 in the middle of the grid of 5s, is never reached by the climbing searches, so it stays out of the answer.

    Testing

    These results come from running the solution:

    heightsResult
    [[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]][[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
    [[1]][[0, 0]]
    [[5, 5, 5], [5, 1, 5], [5, 5, 5]][[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]]
    [[1, 2, 3]][[0, 0], [0, 1], [0, 2]]
    [[3], [2], [1]][[0, 0], [1, 0], [2, 0]]
    [[1, 2], [4, 3]][[0, 1], [1, 0], [1, 1]]

    A flat 200 by 200 grid returns all 40,000 cells.

    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free