Start learning free

LESSON 482 OF 540 · GRAPHS

Pacific Atlantic Water Flow in TypeScript: Two Multi-Source BFS

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

    TYPESCRIPT · GRAPHS

    Pacific Atlantic Water Flow in TypeScript, explained

    Problem overview

    The method pacificAtlantic receives heights, an array of rows of integers: 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 Pacific touches the top and left edges, and the Atlantic the bottom and right edges.

    The method 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 grid in the first example the answer is [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]. For [[1]] it is [[0, 0]], since the only cell touches all four edges. For a ring of 5s around a 1, every ring cell qualifies and the 1 does not: it is lower than all its neighbors, so its water stays where it is.

    The statement 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 every cell's search wanders over the whole lake before giving up.

    Turn the question around. Start at the ocean and climb. If a cell touches the Pacific, its water reaches it. A neighbor whose height is at least as high can send its water down into that cell, and from there to the ocean. So a search that starts from all the Pacific's edge cells at once, and moves to a neighbor only when it is at least as high, visits exactly the cells whose water reaches the Pacific. A second search from the Atlantic's edge cells does the same for the Atlantic. The answer is the cells both searches reach.

    Each search is a breadth-first search that begins with many cells in its queue instead of one. Each cell is marked when it joins the queue, so each is queued at most once. For the first example, the two searches mark these cells (1 means reached):

    pacific        atlantic
1 1 1 1 1      . . . . 1
1 1 1 1 1      . . . 1 1
1 1 1 . .      . . 1 1 1
1 1 . . .      1 1 1 1 1
1 . . . .      1 1 1 1 1

    Cells marked in both grids are exactly the seven in the answer, such as the cell at row 2, column 2 (height 5).

    Step by step

    The lesson writes pacificAtlantic first, assuming a helper reach exists, and then writes the helper.

    1. Store the size: rows is heights.length, and cols is heights[0].length. Every row has the same length.
    2. Call this.reach(heights, 0, 0) and store the grid in pacific. The Pacific touches row 0 and column 0. The helper takes an edge row and an edge column and marks every cell whose water can reach that row or that column.
    3. Call this.reach(heights, rows - 1, cols - 1) for the Atlantic, which touches the last row and the last column. One helper serves both oceans; only the edges differ.
    4. Create result as an empty number[][].
    5. Loop r over the rows. Row by row and left to right within a row is exactly the order the answer needs.
    6. Loop c over the columns.
    7. If both pacific[r][c] and atlantic[r][c] are true, push [r, c] onto result.
    8. Return result.
    9. Write reach as a method of the class, taking heights, edgeRow and edgeCol, and returning a boolean[][].
    10. Store rows and cols again. The variables in pacificAtlantic aren't visible inside this method.
    11. Create seen with Array.from({length: rows}, () => new Array(cols).fill(false)). The arrow function runs once per row, so every row is its own array.
    12. Create queue as an empty number[][] of [row, column] pairs: the cells that were reached but not yet looked around from.
    13. Loop over the rows, then over the columns, to find the cells along the ocean's two edges.
    14. Test r === edgeRow || c === edgeCol. A cell on the edge row or edge column touches the ocean.
    15. Mark it and queue it: set seen[r][c] to true and push [r, c]. A cell is marked when it joins the queue, never later, so no cell is queued twice.
    16. Create directions: [-1, 0] up, [1, 0] down, [0, -1] left, [0, 1] right. Diagonal cells are not neighbors.
    17. Declare head with let, at 0, the index of the next cell to take. This avoids shift(), which would move every remaining element each time.
    18. Loop while head < queue.length. Each cell joins the queue at most once, so this runs at most m · n times.
    19. Unpack the pair at index head into row and col with const [row, col] = queue[head].
    20. Do head++.
    21. Loop over directions with for (const [dr, dc] of directions).
    22. Compute nextRow and nextCol by adding the move to the current position.
    23. Check that the neighbor is on the grid: both coordinates at least 0 and below rows or cols. Cells on the edges have neighbors off the grid, which must be skipped before they are used as indexes.
    24. Check that the search can climb there: !seen[nextRow][nextCol] and heights[nextRow][nextCol] >= heights[row][col]. This is the key line. The search walks against the flow, so a neighbor at least as high can send its water into the current cell.
    25. Mark and queue the neighbor: set seen[nextRow][nextCol] to true and push [nextRow, nextCol].
    26. Return seen after the loop.

    The solution in TypeScript

    class Solution {
    pacificAtlantic(heights: number[][]): number[][] {
        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: number[][] = [];
        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: number[][], edgeRow: number, edgeCol: number): boolean[][] {
        const rows = heights.length;
        const cols = heights[0].length;
        const seen: boolean[][] = Array.from({length: rows}, () => new Array(cols).fill(false));
        const queue: number[][] = [];
        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;
    }
}

    Some TypeScript details:

    • A grid of separate rows. Array.from({length: rows}, () => new Array(cols).fill(false)) calls the arrow function once per row, so each row is a new array. The shortcut new Array(rows).fill(new Array(cols).fill(false)) would put the same row in every position: setting one cell to true would mark that column in every row.
    • Destructuring. const [row, col] = queue[head] takes the two elements of the pair into two variables. for (const [dr, dc] of directions) does the same for each move.
    • pacific[r][c] && atlantic[r][c] works on booleans directly; no comparison with true is needed.
    • Out-of-range reads don't throw. seen[-1] is undefined, and then seen[-1][0] would throw a TypeError. That is why the bounds test comes before the lookups.
    • Types are erased. boolean[][] and number[][] help the compiler but don't exist in the compiled JavaScript.

    Complexity

    Time: O(m · n). Each search marks a cell when it joins the queue, so every cell is queued at most once, and each queued cell looks at four neighbors. Two searches plus the final scan are all O(m · n).

    Space: O(m · n). The grids seen (one per ocean) and the queue each hold at most one entry per cell.

    Edge cases and common mistakes

    • A single cell. [[1]] returns [[0, 0]]: the cell is on every edge.
    • A single row or column. [[1, 2, 3]] returns [[0, 0], [0, 1], [0, 2]], because every cell touches the top and bottom. [[3], [2], [1]] returns [[0, 0], [1, 0], [2, 0]].
    • Equal heights. Water moves between cells of equal height, so the test must be >=. With >, the ring of 5s in the third example would not connect around the border, and the answer would be wrong. A flat 200 by 200 grid returns all 40,000 cells.
    • A cell reaching only one ocean. In [[1, 2], [4, 3]] the answer is [[0, 1], [1, 0], [1, 1]]. The cell at [0, 0] has height 1 and touches the Pacific, but it is not on the bottom or right edge and has no lower neighbor, so it misses the Atlantic.
    • Climbing the wrong way. The search from the ocean moves to higher or equal cells. Moving to lower cells would answer a different question.
    • Using the same seen for both oceans. Each ocean needs its own grid, because the answer is the cells reached by both.
    • Testing the neighbor's coordinates after reading it. Check the bounds first, then seen and heights.
    • Result order. The final scan goes row by row and left to right, which gives reading order without sorting.

    Testing

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