Start learning free

LESSON 482 OF 540 · GRAPHS

Pacific Atlantic Water Flow in Scala: BFS From Both Oceans

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 ArrayBuffer 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

    SCALA · GRAPHS

    Pacific Atlantic Water Flow in Scala, explained

    Problem overview

    The method pacificAtlantic(heights: Array[Array[Int]]): ArrayBuffer[Array[Int]] works on a rectangular island given as a grid of heights, heights(r)(c) for row r and column c, counted from 0 at the top and the left. 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 neighbouring cell (up, down, left or right) when the neighbour's 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 [r, c] pairs in reading order: row by row from the top, left to right inside a row.

    In the first example, the grid is

    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

    and the answer is [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]. For example, [0, 4] sits on the top edge, which is the Pacific, and on the right edge, which is the Atlantic. A single cell, Array(Array(1)), touches all four edges and gives [[0, 0]].

    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.

    The lesson turns the question around. Start from an ocean and climb. A breadth-first search begins at all the cells along the Pacific's edges at once and moves to a neighbour only when the neighbour is at least as high, because water from there can flow down to the cell we are on. Every cell the search reaches can send its water to the Pacific. A second search does the same from the Atlantic's edges. The answer is the cells that both searches reach, listed in reading order. Each search visits every cell at most once, so the total is O(m · n).

    For the first example, the Pacific search marks these cells (T) and leaves the others unmarked (.):

    T T T T T
T T T T T
T T T . .
T T . . .
T . . . .

    And the Atlantic search marks:

    . . . . T
. . . T T
. . T T T
T T T T T
T T T T T

    The cells marked in both grids are exactly the seven listed above.

    Step by step

    1. Store the grid size. rows is heights.length and cols is heights(0).length. Every row has the same length, so the first row's length is the number of columns.
    2. Find the cells that reach the Pacific with reach(heights, 0, 0), stored in pacific. The Pacific touches row 0 and column 0. The helper reach is written after this method; it returns a grid of booleans marking every cell whose water can flow to the given edge row or edge column.
    3. Do the same for the Atlantic with reach(heights, rows - 1, cols - 1), stored in atlantic. One helper serves both oceans; only the edges differ.
    4. Create result, an empty ArrayBuffer[Array[Int]].
    5. Loop over rows, then columns, with r <- 0 until rows and c <- 0 until cols. Row by row and left to right is exactly the order the answer needs.
    6. If pacific(r)(c) and atlantic(r)(c) are both true, append Array(r, c) to result with +=.
    7. Return result as the last expression.
    8. Write reach(heights, edgeRow, edgeCol) with an Array[Array[Boolean]] result. It has its own rows and cols, since the ones in pacificAtlantic are not visible there.
    9. Create seen with Array.fill(rows, cols)(false): rows rows of cols false values. seen(r)(c) becomes true once the search reaches that cell.
    10. Create queue, an empty mutable.Queue[(Int, Int)]. Each element is a cell, a tuple of its row and column.
    11. Seed the queue. Loop over every cell, and where r == edgeRow || c == edgeCol, set seen(r)(c) to true and enqueue (r, c). A cell on the edge row or column touches the ocean, so its water flows straight in. A cell is marked when it joins the queue, never later, so none joins twice.
    12. List the four moves in directions, an Array of (row change, column change) tuples: (-1, 0), (1, 0), (0, -1) and (0, 1). Diagonal cells are not neighbours.
    13. Loop while queue.nonEmpty. Take the front cell with dequeue() and unpack it into row and col with val (row, col) = ....
    14. Loop over the moves, unpacking each into dr and dc, and compute nextRow and nextCol.
    15. Skip positions off the grid. Cells on the edges have neighbours outside, which must not be used as indexes.
    16. Climb when allowed. If the neighbour is not seen yet and heights(nextRow)(nextCol) >= heights(row)(col), mark it seen and enqueue it. This is the key line: the search walks against the flow. Water moves down or level, so a neighbour at least as high can send its water into the current cell, and from there to the ocean.
    17. Return seen after the loop. A true marks exactly the cells whose water can reach this ocean.

    The solution in Scala

    class Solution {
    def pacificAtlantic(heights: Array[Array[Int]]): ArrayBuffer[Array[Int]] = {
        val rows = heights.length
        val cols = heights(0).length
        val pacific = reach(heights, 0, 0)
        val atlantic = reach(heights, rows - 1, cols - 1)
        val result = ArrayBuffer[Array[Int]]()
        for (r <- 0 until rows) {
            for (c <- 0 until cols) {
                if (pacific(r)(c) && atlantic(r)(c)) {
                    result += Array(r, c)
                }
            }
        }
        result
    }

    def reach(heights: Array[Array[Int]], edgeRow: Int, edgeCol: Int): Array[Array[Boolean]] = {
        val rows = heights.length
        val cols = heights(0).length
        val seen = Array.fill(rows, cols)(false)
        val queue = mutable.Queue[(Int, Int)]()
        for (r <- 0 until rows) {
            for (c <- 0 until cols) {
                if (r == edgeRow || c == edgeCol) {
                    seen(r)(c) = true
                    queue.enqueue((r, c))
                }
            }
        }
        val directions = Array((-1, 0), (1, 0), (0, -1), (0, 1))
        while (queue.nonEmpty) {
            val (row, col) = queue.dequeue()
            for ((dr, dc) <- directions) {
                val nextRow = row + dr
                val 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))
                    }
                }
            }
        }
        seen
    }
}

    The Scala details worth a closer look:

    • Two-dimensional arrays are arrays of arrays. seen(r)(c) first takes row r, then element c of it. Writing works the same way: seen(r)(c) = true.
    • Array.fill(rows, cols)(false) builds rows separate rows of cols elements. Changing one row does not touch the others.
    • Tuples. (Int, Int) is a pair type, (r, c) creates one, and val (row, col) = queue.dequeue() and for ((dr, dc) <- directions) take pairs apart in a pattern.
    • enqueue((r, c)) has two pairs of parentheses on purpose: the outer ones are the call, the inner ones create the tuple.
    • mutable and ArrayBuffer come with the lesson. In a file of your own, add import scala.collection.mutable and import scala.collection.mutable.ArrayBuffer.
    • Reading order is free. Because the final loops go row by row, the ArrayBuffer is already sorted as the statement requires. No sorting is needed.

    Complexity

    Let the grid have m rows and n columns.

    Time: O(m · n). Each of the two searches marks a cell once, when it joins the queue, and looks at at most four neighbours when it leaves. The final loop looks at every cell once.

    Space: O(m · n). The two seen grids have m · n entries each, and a queue holds at most m · n cells. The result holds at most as many.

    Edge cases and common mistakes

    • A single cell. Array(Array(1)) gives [[0, 0]]: the cell is on both of the edges that matter.
    • One row or one column. Array(Array(1, 2, 3)) gives [[0, 0], [0, 1], [0, 2]], every cell, because each touches the top edge and the bottom edge. Array(Array(3), Array(2), Array(1)) gives [[0, 0], [1, 0], [2, 0]].
    • Equal heights flow. A grid of four 1s, Array(Array(1, 1), Array(1, 1)), gives all four cells. The condition is >= when climbing, not >. In the grid of 5s with a 1 in the middle, the 5s pass water along the border, and the 1 is left out: it is lower than every neighbour, so the search never climbs into it, and the answer is the eight border cells.
    • Climbing the wrong way. Moving to a neighbour that is at least as low follows the water down from the ocean, which answers a different question.
    • Marking cells when they leave the queue. A cell could then be queued many times by different neighbours. Mark it when it joins.
    • Swapping the oceans' edges. The Pacific is the top row and left column. The Atlantic is the bottom row and right column. Using the grid's rows for columns and vice versa breaks non-square grids.
    • Checking bounds after indexing. Reading seen(nextRow)(nextCol) for a position outside the grid throws an ArrayIndexOutOfBoundsException, so the range check comes first.

    Testing

    • The 5 by 5 grid above gives [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]].
    • Array(Array(1)) gives [[0, 0]].
    • Array(Array(5, 5, 5), Array(5, 1, 5), Array(5, 5, 5)) gives [[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]].
    • Array(Array(1, 2, 3)) gives [[0, 0], [0, 1], [0, 2]].
    • Array(Array(3), Array(2), Array(1)) gives [[0, 0], [1, 0], [2, 0]].
    • Array(Array(1, 1), Array(1, 1)) gives [[0, 0], [0, 1], [1, 0], [1, 1]].
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free