Start learning free

LESSON 478 OF 536 · GRAPHS

Pacific Atlantic Water Flow in JavaScript: BFS from the Oceans 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 array 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 27
    Ctrl + Enter to check

    JAVASCRIPT · GRAPHS

    Pacific Atlantic Water Flow in JavaScript, 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 a grid heights with m rows and n columns, and heights[r][c] is the height of the cell in row r and column c, with rows counted from the top and columns from the left.

    Rain falls on every cell. Water flows from a cell to a neighbor above, below, left or right when the neighbor's 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(heights) returns the cells from which water can reach both oceans, as [r, c] pairs in reading order: row by row from the top, left to right within a row.

    For the 5 by 5 example grid 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 (Pacific) and the right edge (Atlantic). From [2, 2], height 5, water runs up to the Pacific and right to the Atlantic. The cell [2, 1], height 4, reaches the Pacific through [2, 0], but every path to the Atlantic needs a step up.

    The lesson asks for O(m · n) time and O(m · n) extra space.

    Approach: climb up from the oceans

    The direct idea follows the water down from every cell, one search per cell. That can cost O((m · n)²): picture a large flat lake in the middle of the island, where each cell's search wanders over the whole lake before giving up.

    Turning the question around fixes this. Instead of asking where a cell's water goes, ask which cells can send water to the Pacific. Start at the cells along the Pacific's edges and move against the flow: step to a neighbor only when it is at least as high as the current cell, because water from that neighbor can flow down to the current cell and on to the ocean. A breadth-first search (BFS) that starts from all the edge cells at once marks every cell that can reach the Pacific. A second search from the Atlantic's edges does the same for the Atlantic. The answer is the cells that both searches reached. Each search visits every cell at most once.

    On the 5 by 5 example, the two searches mark these cells (1 means reached):

    Pacific   Atlantic
11111     ....1
11111     ...11
111..     ..111
11...     11111
1....     11111

    The cells marked in both pictures are exactly the seven in the answer.

    Step by step

    1. Store the grid size. rows = heights.length and cols = heights[0].length; every row has the same length.
    2. Search from the Pacific. this.reach(heights, 0, 0) returns a grid of booleans for the cells whose water reaches row 0 or column 0. The helper is written afterwards.
    3. Search from the Atlantic. this.reach(heights, rows - 1, cols - 1) does the same for the last row and the last column. One helper serves both oceans; only the edges differ.
    4. Create result, an empty array.
    5. Loop over rows, then columns. Row by row and left to right is the order the answer must be in.
    6. Collect the cells reached by both. If pacific[r][c] and atlantic[r][c] are both true, push [r, c].
    7. Return result.
    8. Write reach(heights, edgeRow, edgeCol) as a second method of the class. It returns a grid of booleans.
    9. Store the size again. The variables of pacificAtlantic aren't visible inside reach.
    10. Create seen, a grid of false values, with Array.from({length: rows}, () => new Array(cols).fill(false)). The arrow function runs once per row, so every row is its own array.
    11. Create queue, an empty array of [row, column] pairs: the cells reached but not yet looked around from.
    12. Seed the search. Loop over all cells, and for every cell with r === edgeRow || c === edgeCol, which touches the ocean, set seen[r][c] to true and push [r, c]. A cell is marked when it joins the queue, never later, so no cell joins the queue twice.
    13. List the four moves in directions as [row change, column change] pairs: up, down, left, right.
    14. Use an index head, starting at 0, for the next cell to take from the queue. It avoids shift(), which moves every remaining element.
    15. Loop while head < queue.length. Each cell joins the queue at most once, so this runs at most m · n times.
    16. Take the next cell with const [row, col] = queue[head] and do head++.
    17. Try each move, unpacking it as [dr, dc], and compute nextRow = row + dr and nextCol = col + dc.
    18. Skip positions off the grid. Cells on the edges have neighbors outside the grid.
    19. Climb when allowed. If the neighbor isn't seen yet and heights[nextRow][nextCol] >= heights[row][col], mark it and push it. This is the key line: the search walks against the flow.
    20. Return seen.

    The solution in JavaScript

    class Solution {
    pacificAtlantic(heights) {
        const rows = heights.length;
        const cols = heights[0].length;
        const pacific = this.reach(heights, 0, 0);
        const atlantic = this.reach(heights, rows - 1, cols - 1);
        const result = [];
        for (let r = 0; r < rows; r++) {
            for (let c = 0; c < cols; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.push([r, c]);
                }
            }
        }
        return result;
    }

    reach(heights, edgeRow, edgeCol) {
        const rows = heights.length;
        const cols = heights[0].length;
        const seen = Array.from({length: rows}, () => new Array(cols).fill(false));
        const queue = [];
        for (let r = 0; r < rows; r++) {
            for (let c = 0; c < cols; c++) {
                if (r === edgeRow || c === edgeCol) {
                    seen[r][c] = true;
                    queue.push([r, c]);
                }
            }
        }
        const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
        let head = 0;
        while (head < queue.length) {
            const [row, col] = queue[head];
            head++;
            for (const [dr, dc] of directions) {
                const nextRow = row + dr;
                const nextCol = col + dc;
                if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
                    if (!seen[nextRow][nextCol] && heights[nextRow][nextCol] >= heights[row][col]) {
                        seen[nextRow][nextCol] = true;
                        queue.push([nextRow, nextCol]);
                    }
                }
            }
        }
        return seen;
    }
}

    JavaScript details worth knowing:

    • Building a grid. new Array(rows).fill(new Array(cols).fill(false)) would put the same row array in every row. Marking one cell would then mark the whole column. For example, after bad[0][1] = true on such a 2 by 3 grid, both rows print as [false, true, false]. Array.from with an arrow function creates a new row each time.
    • Destructuring. const [row, col] = queue[head] takes the two elements of the pair into two variables, and for (const [dr, dc] of directions) does the same for each move.
    • Out-of-range indexes. Reading heights[-1] gives undefined, and indexing into that throws a TypeError. The bounds test comes first, and && stops at the first false check, so the arrays are indexed only when the position is inside the grid.
    • A cell may be queued from two edges. A corner such as the top-left cell touches both the edge row and the edge column. The loop marks it once, because the condition is one if with ||.
    • Numbers compare numerically, so >= on heights needs no conversion.

    Complexity

    Time: O(m · n). Each of the two searches marks every cell at most once, and for each queued cell looks at four neighbors. The final loop over the grid is O(m · n) too.

    Space: O(m · n). Each search has a grid of booleans and a queue of at most m · n pairs.

    Edge cases and common mistakes

    • One cell. [[1]] returns [[0, 0]]: the cell touches all four edges.
    • Equal heights. Water flows between cells of equal height, so the test is >= when climbing, not >. In [[5, 5, 5], [5, 1, 5], [5, 5, 5]] all the 5s pass the water along the border, and the answer holds all cells except the middle 1, which is lower than all its neighbors.
    • A single row or column. [[1, 2, 3]] returns [[0, 0], [0, 1], [0, 2]]: every cell is on the top edge, which is the Pacific, and on the bottom edge, which is the Atlantic. [[1], [2], [3]] works the same way.
    • Climbing in the wrong direction. Moving to lower neighbors from the ocean checks where water could flow from the ocean, which is not the question. The search must go to neighbors at least as high.
    • Marking cells late. Marking a cell when it leaves the queue, rather than when it joins, can queue it several times.
    • Result order. Collecting the cells while scanning rows, then columns, already gives reading order. No sort is needed.
    • Swapped edges. The Atlantic is the last row and the last column: rows - 1 and cols - 1.

    Testing

    • [[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]] gives [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]].
    • [[1]] gives [[0, 0]].
    • [[5, 5, 5], [5, 1, 5], [5, 5, 5]] gives [[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]].
    • [[1, 2, 3]] gives [[0, 0], [0, 1], [0, 2]].
    • [[1], [2], [3]] gives [[0, 0], [1, 0], [2, 0]].
    • [[1, 2], [4, 3]] gives [[0, 1], [1, 0], [1, 1]].
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free