Start learning free

LESSON 481 OF 539 · GRAPHS

Pacific Atlantic Water Flow in C#: Two Breadth-First Searches

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 a List 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

    PacificAtlantic receives heights, an int[][] grid of cell heights. The Pacific Ocean touches the top and left edges, and the Atlantic touches the bottom and right edges. Rain falls on every cell. Water flows from a cell to a neighbor (up, down, left or right) whose height is less than or equal to the cell's, and from any edge cell into the ocean that touches that edge.

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

    In the 5x5 example, [0, 4] is on the top edge (Pacific) and the right edge (Atlantic), so it qualifies at once. The cell [2, 1], height 4, reaches the Pacific through [2, 0], but every path to the Atlantic needs a step up, so it does not. In the 3x3 grid of 5s with a 1 in the middle, the 5s pass water along the border to both oceans because water may flow between equal heights, while the 1 is lower than all its neighbors and keeps its water.

    Approach: climb up from the oceans

    Following the water down from every cell costs one search per cell, up to O((m * n)^2) in total: in a large flat lake, each cell's search wanders over the whole lake before giving up.

    Turn the question around. Start from the ocean and move against the flow. A breadth-first search begins from all the cells along the Pacific's edges at once, and moves to a neighbor only when the neighbor is at least as high, because water from that neighbor can flow down into the current cell and onward. Every cell it reaches can send water to the Pacific. A second search does the same from the Atlantic's edges. The answer is the cells both searches reach, and each search visits every cell at most once.

    For the 5x5 example, the Pacific search marks these cells (P), and the Atlantic search marks these (A):

    PPPPP    ....A
PPPPP    ...AA
PPP..    ..AAA
PP...    AAAAA
P....    AAAAA

    The cells marked in both grids are [0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1] and [4, 0].

    Step by step

    The lesson writes the main method first, assuming a helper Reach, then the helper.

    1. Store the size. rows is heights.Length, and cols is heights[0].Length, since every row has the same length.
    2. Find the Pacific cells: Reach(heights, 0, 0) into a bool[,] named pacific. The Pacific touches row 0 and column 0.
    3. Find the Atlantic cells: Reach(heights, rows - 1, cols - 1) into atlantic. One helper serves both oceans; only the edges differ.
    4. Create result, an empty List<List<int>>.
    5. Loop over rows, then columns. Scanning row by row and left to right gives exactly the required order.
    6. Collect the cells. If pacific[r, c] and atlantic[r, c] are both true, add new List<int> { r, c }. Then return result.
    7. Write Reach. It takes the grid and an edge row and column, and returns a bool[,], a two-dimensional array read as seen[r, c].
    8. Prepare the search. Recompute rows and cols (the helper cannot see the main method's variables), create seen as new bool[rows, cols], and a Queue<(int, int)> whose elements are (row, column) tuples.
    9. Seed the queue with the ocean's edges. For every cell with r == edgeRow || c == edgeCol, set seen[r, c] to true and enqueue (r, c). A cell is marked when it joins the queue, so none joins twice.
    10. Define the four moves as an array (int, int)[] directions: (-1, 0), (1, 0), (0, -1), (0, 1). Diagonal cells are not neighbors.
    11. Loop while queue.Count > 0. Take the front cell and deconstruct it: (int row, int col) = queue.Dequeue();.
    12. Try each move, unpacking it into dr and dc, and compute nextRow and nextCol.
    13. Skip cells off the grid by checking both indexes against 0 and the size.
    14. Climb only against the flow. If the neighbor is not seen and heights[nextRow][nextCol] >= heights[row][col], mark it and enqueue it.
    15. Return seen.

    The solution in C#

    class Solution {
    public List<List<int>> PacificAtlantic(int[][] heights) {
        int rows = heights.Length;
        int cols = heights[0].Length;
        bool[,] pacific = Reach(heights, 0, 0);
        bool[,] atlantic = Reach(heights, rows - 1, cols - 1);
        List<List<int>> result = new List<List<int>>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (pacific[r, c] && atlantic[r, c]) {
                    result.Add(new List<int> { r, c });
                }
            }
        }
        return result;
    }

    public bool[,] Reach(int[][] heights, int edgeRow, int edgeCol) {
        int rows = heights.Length;
        int cols = heights[0].Length;
        bool[,] seen = new bool[rows, cols];
        Queue<(int, int)> queue = new Queue<(int, int)>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (r == edgeRow || c == edgeCol) {
                    seen[r, c] = true;
                    queue.Enqueue((r, c));
                }
            }
        }
        (int, int)[] directions = { (-1, 0), (1, 0), (0, -1), (0, 1) };
        while (queue.Count > 0) {
            (int row, int col) = queue.Dequeue();
            foreach ((int dr, int dc) in 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;
                        queue.Enqueue((nextRow, nextCol));
                    }
                }
            }
        }
        return seen;
    }
}

    The C# details worth knowing:

    • Two array shapes. The input int[][] is jagged, read as heights[r][c]. The result bool[,] is rectangular, read as seen[r, c]. Mixing the two notations is a compile error.
    • Tuples. (int, int) is a value tuple. (int row, int col) = queue.Dequeue(); deconstructs it into two variables, and foreach ((int dr, int dc) in directions) does the same for each move.
    • Array initializer. (int, int)[] directions = { (-1, 0), (1, 0), (0, -1), (0, 1) }; needs no new when it is the initializer of a declaration.
    • The index checks come first. seen and heights would throw IndexOutOfRangeException for an off-grid index, so the bounds if wraps the other one.
    • No recursion. The queue replaces the call stack, so a 200x200 grid cannot overflow it.

    Complexity

    Time: O(m * n). Each search marks a cell once, enqueues it once and looks at its four neighbors once. Building the answer is another m * n pass.

    Space: O(m * n) for the two seen grids and the queue.

    Edge cases and common mistakes

    • One cell. {{1}} returns [[0,0]]: the cell touches all four edges.
    • One row. {{1,2,3,4}} returns all four cells, because every cell of a single row touches the top and the bottom edge.
    • One column. {{4},{3},{2}} returns all three cells for the same reason.
    • Equal heights. The comparison is >=, not >, because water crosses between equal cells. With > the 3x3 example would lose its border cells.
    • Wrong direction. Moving to lower neighbors from the ocean edge would follow the flow's direction in reverse. The search climbs, since water from a higher neighbor can flow down into the cell.
    • Marking when dequeuing. Marking a cell only when it leaves the queue lets it be enqueued several times.
    • Order of the answer. Collecting cells while searching gives the wrong order. The final double loop gives reading order.

    Testing

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