Start learning free

LESSON 482 OF 540 · GRAPHS

Pacific Atlantic Water Flow in Go: 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 a slice 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

    GO · GRAPHS

    Pacific Atlantic Water Flow in Go, 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 of m rows and n columns, given as heights, where heights[r][c] is the height of the cell in row r and column c. Rows count from 0 at the top, columns from 0 at 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 function pacificAtlantic returns the cells from which water can reach both oceans, as a slice 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 result 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, so it touches both oceans. The cell [2, 1], of height 4, reaches the Pacific through [2, 0], but every path to the Atlantic needs a step up, so it is not in the answer. For [[1]] the answer is [[0 0]]: the only cell touches all four edges. For a ring of 5s around a single 1, water passes between equal heights along the border, so every cell except the middle one qualifies.

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

    Approach: climb up from each ocean

    Following the water down from every cell, one search per cell, can cost O((m · n)²). Think of a big flat lake in the middle of the island: each cell's search wanders over the whole lake before it gives up.

    Turn the question around and climb up from the oceans. Start a breadth-first search from all the cells along the Pacific's edges at once. Move from a cell to a neighbor only when the neighbor is at least as high, because the water of that higher neighbor can flow down into the current cell and on to the ocean. Every cell the search reaches can send its water to the Pacific. Run a second search from the Atlantic's edges. The answer is the cells that both searches reach. Each search visits every cell at most once.

    The same helper serves both oceans. It takes an edge row and an edge column: (0, 0) for the Pacific, and (rows - 1, cols - 1) for the Atlantic. A cell is on the ocean's edge when its row is the edge row or its column is the edge column.

    Step by step

    The main function

    1. Store the grid's size: rows is len(heights) and cols is len(heights[0]). Every row has the same length, so the first row gives the number of columns.
    2. Call reach(heights, 0, 0) and store the result in pacific. The Pacific touches row 0 and column 0. The helper returns a grid of bools that marks every cell whose water can reach that row or column.
    3. Call reach(heights, rows - 1, cols - 1) for the Atlantic, in atlantic.
    4. Create result as an empty slice of []int pairs, [][]int{}.
    5. Loop over the rows and, inside, over the columns. Row by row, left to right, is exactly the order the answer needs.
    6. If pacific[r][c] && atlantic[r][c], append []int{r, c} to result.
    7. Return result.

    The helper reach

    1. Write the signature: reach takes heights [][]int, edgeRow int and edgeCol int, and returns a [][]bool.
    2. Store rows and cols again. They are the helper's own variables, since the ones in pacificAtlantic are not visible here.
    3. Create seen with make([][]bool, rows). That makes only the outer slice, and its rows are nil until each is made. seen[r][c] becomes true once the search has reached that cell.
    4. Create queue as an empty [][2]int. Each element is a cell, its row and its column. [2]int is an array of exactly two ints, a good fit for a cell.
    5. Loop over the rows and create each row of seen with make([]bool, cols), all false.
    6. Loop over the columns and test r == edgeRow || c == edgeCol: the cell touches the ocean, so its water flows straight into it.
    7. Mark such a cell in seen and append [2]int{r, c} to the queue. A cell is marked when it joins the queue, never later, so no cell joins twice.
    8. Create directions, the four moves as [2]int pairs of row change and column change: up, down, left and right. Diagonal cells are not neighbors.
    9. Loop while the queue is not empty. Take cell := queue[0], drop it with queue = queue[1:], and copy its values into row, col := cell[0], cell[1].
    10. Loop over the directions and compute nextRow := row + d[0] and nextCol := col + d[1].
    11. Check the neighbor is inside the grid: nextRow and nextCol are at least 0 and below rows and cols. Cells on the edges have neighbors off the grid, which must be skipped before they are used as indexes.
    12. Climb only when allowed: the neighbor is not in seen and heights[nextRow][nextCol] >= heights[row][col]. This is the key line: the search walks against the flow, and water moves down or level.
    13. Mark the neighbor and queue it. Its own neighbors are checked when it leaves the queue.
    14. Return seen. true marks exactly the cells whose water reaches this ocean.

    The solution in Go

    func pacificAtlantic(heights [][]int) [][]int {
    rows := len(heights)
    cols := len(heights[0])
    pacific := reach(heights, 0, 0)
    atlantic := reach(heights, rows - 1, cols - 1)
    result := [][]int{}
    for r := 0; r < rows; r++ {
        for c := 0; c < cols; c++ {
            if pacific[r][c] && atlantic[r][c] {
                result = append(result, []int{r, c})
            }
        }
    }
    return result
}

func reach(heights [][]int, edgeRow int, edgeCol int) [][]bool {
    rows := len(heights)
    cols := len(heights[0])
    seen := make([][]bool, rows)
    queue := [][2]int{}
    for r := 0; r < rows; r++ {
        seen[r] = make([]bool, cols)
        for c := 0; c < cols; c++ {
            if r == edgeRow || c == edgeCol {
                seen[r][c] = true
                queue = append(queue, [2]int{r, c})
            }
        }
    }
    directions := [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
    for len(queue) > 0 {
        cell := queue[0]
        queue = queue[1:]
        row, col := cell[0], cell[1]
        for _, d := range directions {
            nextRow := row + d[0]
            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 = append(queue, [2]int{nextRow, nextCol})
                }
            }
        }
    }
    return seen
}

    The Go details worth a closer look:

    • Nested slices need a make per row. make([][]bool, rows) gives rows nil slices. The loop then sets seen[r] to a fresh make([]bool, cols). Writing seen[r][c] before that would panic with an index out of range.
    • Arrays as cells. [2]int is an array, a value type, so each queue entry holds its two numbers directly and copying a cell copies both numbers. A [][2]int literal such as {{-1, 0}, {1, 0}, {0, -1}, {0, 1}} can leave out the inner type.
    • Tuple assignment. row, col := cell[0], cell[1] declares both variables in one line.
    • The result is never empty. The top-right and bottom-left corners touch both oceans, so every grid has at least those two cells (one cell when the grid has one). The code starts from [][]int{}, an empty slice that is not nil, and appends to it.
    • || and && short-circuit. In the bounds check, the index is used only after the range tests pass.

    Complexity

    Time: O(m · n). Each search marks a cell when it joins the queue, so every cell is queued at most once, and for each queued cell the code looks at 4 neighbors. Two searches and one scan of the grid add up to a constant times m · n.

    Space: O(m · n). Each seen grid has one bool per cell, and a queue holds at most m · n cells. The result holds at most m · n pairs.

    Edge cases and common mistakes

    • Climbing with > instead of >=. Water flows between cells of equal height, so the search must too. With a strict comparison, the Pacific search in the third example would never reach [1, 2] from [0, 2], and that cell would be lost from the answer.
    • Flowing the wrong way. The search starts at the ocean, so it moves to the same or higher cells. Moving to lower ones would answer a different question.
    • A single row or column. In [[1, 2, 3]] the one row is both the top and the bottom edge, so every cell touches both oceans and the answer is [[0 0] [0 1] [0 2]]. A single column works the same way.
    • Lakes. The 1 in the middle of the ring is lower than all its neighbors, so its water stays where it is and it is left out.
    • Marking when taken out of the queue. If a cell is marked only when it leaves the queue, it can join the queue several times. Marking at the moment of joining avoids that.
    • Order of the result. The loops over r and c produce reading order with no sorting.

    Testing

    For the first example, the cells marked by the Pacific search are 1, the others a dot:

    1 1 1 1 1
1 1 1 1 1
1 1 1 . .
1 1 . . .
1 . . . .

    The Atlantic search marks:

    . . . . 1
. . . 1 1
. . 1 1 1
1 1 1 1 1
1 1 1 1 1

    The cells marked in both grids are the answer: [0 4], [1 3], [1 4], [2 2], [3 0], [3 1] and [4 0]. More inputs, with the results the function returns:

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