Start learning free

LESSON 477 OF 535 · GRAPHS

Pacific Atlantic Water Flow in C++: Two Multi-Source BFS Runs

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: a vector of rows, where each row is a vector 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 a vector 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 25
    Ctrl + Enter to check

    C++ · GRAPHS

    Pacific Atlantic Water Flow in C++, explained

    Problem overview

    The function pacificAtlantic receives heights, a vector<vector<int>> where heights[r][c] is the height of the cell in row r and column c. Rows are numbered from 0 at the top and columns from 0 at the left. Rain falls on every cell. Water flows from a cell to a neighbouring cell (up, down, left or right) when the neighbour'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 touches the bottom and right edges.

    The function returns the cells from which water can reach both oceans, as a vector of {r, c} pairs in reading order: row by row from the top, and left to right within a row.

    For the 5x5 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] sits on the top edge and the right edge. From [2, 2], height 5, water runs up to the Pacific and right to the Atlantic. For [[1]] the answer is [[0, 0]], since the only cell touches every edge. In the grid of 5s with a 1 in the middle, the 1 is lower than all its neighbours, so its water stays where it is, and the eight 5s are the answer because water passes between cells of equal height.

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

    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.

    Turn the question around. Instead of asking where a cell's water goes, ask which cells can send water to a given ocean. Start from the cells along that ocean's edges, since their water flows straight in. From a cell, move to a neighbour only when the neighbour is at least as high: water from there can flow down (or stay level) into the cell we came from, and from there on to the ocean. Every cell the search reaches can send its water to that ocean.

    That is a BFS that starts from many cells at once, all the edge cells of one ocean, in the same queue. A seen grid marks the cells already reached, so each cell is queued at most once. Run it for the Pacific and again for the Atlantic. The answer is the cells that both searches reached. A single helper, reach, serves both oceans, because only the edges differ: the Pacific is row 0 and column 0, and the Atlantic is the last row and the last column.

    The answers come out in reading order for free, because the final loop goes through the rows from the top and through the columns from the left.

    Step by step

    1. Store the size. rows is heights.size() and cols is heights[0].size(), both in ints. Every row has the same length.
    2. Find the Pacific cells: reach(heights, 0, 0) stored in a vector<vector<bool>> named pacific. The lesson uses reach before writing it: given an edge row and an edge column, it returns a grid marking every cell whose water can flow to them.
    3. Find the Atlantic cells: reach(heights, rows - 1, cols - 1) in atlantic.
    4. Create result, an empty vector<vector<int>>.
    5. Loop over the rows with r, then over the columns with c inside it.
    6. Collect the cells reached by both. When pacific[r][c] and atlantic[r][c] are both true, push {r, c} onto result.
    7. Return result.
    8. Write reach as a method taking vector<vector<int>>& heights and two ints, edgeRow and edgeCol, returning a vector<vector<bool>>.
    9. Store the size again in the helper's own rows and cols, because the variables of the other method aren't visible here.
    10. Create seen with rows rows, each a vector<bool> of cols falses.
    11. Create the queue, queue<pair<int, int>> q, where each element is a cell's row and column.
    12. Seed the search. Loop over every cell. When r == edgeRow || c == edgeCol, the cell touches the ocean: set seen[r][c] to true and push {r, c}. A cell is marked when it joins the queue, so it never joins twice.
    13. Define the four moves in a vector<pair<int, int>> named directions: {-1, 0}, {1, 0}, {0, -1} and {0, 1}. Diagonal cells aren't neighbours.
    14. Loop while the queue isn't empty. Unpack the front with auto [row, col] = q.front() and then call q.pop().
    15. Loop over the moves, unpacking each into dr and dc, and compute nextRow = row + dr and nextCol = col + dc.
    16. Skip positions off the grid: both coordinates must be at least 0 and below rows or cols.
    17. Climb when allowed: the neighbour isn't seen and heights[nextRow][nextCol] >= heights[row][col]. This is the key line. The search walks against the flow.
    18. Mark and queue the neighbour. Its own neighbours are checked when it leaves the queue.
    19. Return seen after the loop.

    The solution in C++

    class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int rows = heights.size();
        int cols = heights[0].size();
        vector<vector<bool>> pacific = reach(heights, 0, 0);
        vector<vector<bool>> atlantic = reach(heights, rows - 1, cols - 1);
        vector<vector<int>> result;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.push_back({r, c});
                }
            }
        }
        return result;
    }

    vector<vector<bool>> reach(vector<vector<int>>& heights, int edgeRow, int edgeCol) {
        int rows = heights.size();
        int cols = heights[0].size();
        vector<vector<bool>> seen(rows, vector<bool>(cols, false));
        queue<pair<int, int>> q;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == edgeRow || c == edgeCol) {
                    seen[r][c] = true;
                    q.push({r, c});
                }
            }
        }
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!q.empty()) {
            auto [row, col] = q.front();
            q.pop();
            for (auto [dr, dc] : directions) {
                int nextRow = row + dr;
                int 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;
                        q.push({nextRow, nextCol});
                    }
                }
            }
        }
        return seen;
    }
};

    The C++ details worth a closer look:

    • seen(rows, vector<bool>(cols, false)). The second argument is the value every row starts as, so each row gets its own copy of it. The result is rows independent rows of cols falses.
    • Structured bindings. auto [row, col] = q.front() names the two members of the pair. It needs C++17. The binding copies the pair, so popping the queue on the next line is safe. pop returns nothing, so the front has to be read first.
    • Brace initialisation. q.push({r, c}) builds a pair<int, int> in place, and result.push_back({r, c}) builds a vector<int> with two elements. The same braces make different types, depending on what the container expects.
    • Passing by reference. vector<vector<int>>& heights lets the helper read the grid without copying up to 40,000 numbers on each call.
    • Returning a large vector by value. return seen moves the local grid out; it isn't copied.
    • vector<bool> is bit-packed. It works as a grid of booleans here, but its elements are proxies, so you can't take a bool& to one.

    Complexity

    Time: O(m · n). Each BFS marks a cell when it joins the queue, so a cell is queued at most once and each queue pop looks at four neighbours. The seeding loop and the final loop also visit each cell once. Two searches and two passes are still a constant multiple of m · n.

    Space: O(m · n). The two seen grids and the queue each hold up to m · n entries, and the result is at most that large.

    Edge cases and common mistakes

    • A single cell. [[1]] gives [[0, 0]]: the cell is on the edge row and the edge column for both oceans.
    • A single row or column. [[1, 2, 3]] gives all three cells, [[0, 0], [0, 1], [0, 2]], because every cell touches both the top and bottom edges. A column such as [[3], [2], [1]] gives [[0, 0], [1, 0], [2, 0]] for the same reason.
    • Equal heights. Water flows between equal cells, so the test is >=, not >. With a strict comparison the 5s of the third example wouldn't pass water along the border.
    • Climbing the wrong way. The search must go to neighbours that are at least as high. Going to lower ones would mark the cells the ocean's water can't reach.
    • Marking when popping. Marking a cell only when it leaves the queue lets it be queued many times. Mark it when it joins.
    • Row and column order. The answer pairs are {r, c}, row first. Swapping them gives wrong cells on non-square grids, such as [[1, 2], [4, 3]], whose answer is [[0, 1], [1, 0], [1, 1]].
    • Forgetting the bounds check. Cells on the edges have neighbours outside the grid, and reading them is undefined behaviour in C++, not an exception.

    Testing

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