Start learning free

LESSON 482 OF 540 · GRAPHS

Pacific Atlantic Water Flow in Kotlin: Two BFS Passes 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 an ArrayList 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

    KOTLIN · GRAPHS

    Pacific Atlantic Water Flow in Kotlin, explained

    Problem overview

    A rectangular island sits 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 heights, an Array<IntArray> where heights[r][c] is the height of the cell in row r and column c. 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 edge cell into the ocean that touches that edge.

    pacificAtlantic returns the cells from which water can reach 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.

    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]]. For [[1]] it is [[0, 0]], because the single cell touches all four edges. For a ring of 5s around a single 1, every cell except the middle one qualifies: water passes along equal heights, and the 1 is lower than all its neighbors, so its water stays where it is.

    Approach

    The direct way follows the water down from each cell with a search of its own. That can cost O((m · n)²): on a large flat lake in the middle of the island, each cell's search wanders over the whole lake before giving up.

    Turning the question around fixes this. Instead of asking where a cell's water goes, ask which cells can send water to the Pacific, and start from the Pacific. A breadth-first search begins at all cells along the Pacific's two edges at once and moves to a neighbor only when the neighbor is at least as high as the current cell, because water from that neighbor can then flow down to the current cell and on to the ocean. Every cell the search reaches can reach the Pacific. A second search does the same from the Atlantic's edges. The answer is the cells that both searches reach. Each search visits every cell at most once, so the total is O(m · n).

    The two grids the searches produce for the first example, from a real run (1 means the cell's water reaches that ocean):

    pacific:      atlantic:
1 1 1 1 1     0 0 0 0 1
1 1 1 1 1     0 0 0 1 1
1 1 1 0 0     0 0 1 1 1
1 1 0 0 0     1 1 1 1 1
1 0 0 0 0     1 1 1 1 1

    The cells that hold a 1 in both grids are the seven in the answer, such as [2, 2], whose height is 5.

    Step by step

    The main function pacificAtlantic does the following:

    1. Store the size. rows = heights.size and cols = heights[0].size. Every row has the same length, so the first row gives the number of columns.
    2. Find the Pacific cells. reach(heights, 0, 0) returns a boolean grid. The Pacific touches row 0 and column 0.
    3. Find the Atlantic cells. reach(heights, rows - 1, cols - 1). The Atlantic touches the last row and the last column. One helper serves both oceans; only the edges differ.
    4. Collect the answer. result is a mutableListOf<List<Int>>(). Two nested loops walk the grid row by row, left to right, which is the required order. A cell is added as listOf(r, c) when both grids hold true for it.
    5. Return result.

    The helper reach(heights, edgeRow, edgeCol) is the BFS:

    1. Create seen. Array(rows) { BooleanArray(cols) } gives every row its own array, all false. A cell is marked when it joins the queue, so it never joins twice.
    2. Create the queue. ArrayDeque<Pair<Int, Int>>(); each element is a cell, a Pair of row and column.
    3. Seed it with the ocean's edge cells. Loop over every cell and test r == edgeRow || c == edgeCol. Those cells touch the ocean, so mark them and add Pair(r, c).
    4. List the four moves. arrayOf(Pair(-1, 0), Pair(1, 0), Pair(0, -1), Pair(0, 1)): up, down, left and right. Diagonal cells are not neighbors.
    5. Loop while the queue is not empty. Take the front cell with removeFirst() and unpack it: val (row, col) = ....
    6. Try each move. for ((dr, dc) in directions), with nextRow = row + dr and nextCol = col + dc.
    7. Stay inside the grid. Check that both new indexes are at least 0 and below rows or cols, before using them as indexes.
    8. Climb when allowed. If the neighbor is not seen and heights[nextRow][nextCol] >= heights[row][col], mark it and add it to the queue. This is the key line: the search walks against the flow.
    9. Return seen.

    The solution in Kotlin

    class Solution {
    fun pacificAtlantic(heights: Array<IntArray>): List<List<Int>> {
        val rows = heights.size
        val cols = heights[0].size
        val pacific = reach(heights, 0, 0)
        val atlantic = reach(heights, rows - 1, cols - 1)
        val result = mutableListOf<List<Int>>()
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.add(listOf(r, c))
                }
            }
        }
        return result
    }
    fun reach(heights: Array<IntArray>, edgeRow: Int, edgeCol: Int): Array<BooleanArray> {
        val rows = heights.size
        val cols = heights[0].size
        val seen = Array(rows) { BooleanArray(cols) }
        val queue = ArrayDeque<Pair<Int, Int>>()
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (r == edgeRow || c == edgeCol) {
                    seen[r][c] = true
                    queue.add(Pair(r, c))
                }
            }
        }
        val directions = arrayOf(Pair(-1, 0), Pair(1, 0), Pair(0, -1), Pair(0, 1))
        while (queue.isNotEmpty()) {
            val (row, col) = queue.removeFirst()
            for ((dr, dc) in 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.add(Pair(nextRow, nextCol))
                    }
                }
            }
        }
        return seen
    }
}

    Kotlin details worth knowing:

    • Array(rows) { BooleanArray(cols) } runs the block once per row, so each row is a separate array. Repeating one array object would make all the rows share the same cells.
    • Destructuring. A Pair supports val (row, col) = pair, which names its two parts. The same works in the loop header: for ((dr, dc) in directions).
    • Return types. The function returns List<List<Int>>. The mutableListOf list is returned as a read-only List, and listOf(r, c) builds each pair.
    • Short-circuit checks. In the bounds test, && stops at the first false condition. The height comparison sits in a second if, which only runs once the indexes are known to be valid.
    • ArrayDeque is Kotlin's own, with add at the back and removeFirst at the front.

    Complexity

    Each call of reach marks a cell when it joins the queue, so a cell is queued at most once and examined with four moves: O(m · n) time. The function calls it twice and then walks the grid once, which stays O(m · n). The two seen grids, the queue and the result take O(m · n) extra space.

    Edge cases and common mistakes

    • Climbing with > instead of >=. Water also flows between cells of equal height. With a strict comparison the ring of 5s would not be passed along, and the answer would lose cells.
    • Comparing in the wrong direction. The search starts at the ocean and goes uphill, so the neighbor must be at least as high as the current cell. Using <= would follow the water downhill from the ocean, which answers a different question.
    • Seeding only one edge. The Pacific is the top row and the left column; skipping one of them loses cells that reach the ocean only through that edge.
    • Marking cells when they leave the queue. A cell could then be queued several times. Marking as it joins keeps each cell to one entry.
    • Single cell. [[1]] gives [[0, 0]]: the cell is on every edge.
    • Single row or column. Every cell touches one ocean through its row or column edge, and often both. [[1, 2, 3, 4]] gives all four cells, and so does the column [[4], [3], [2]] with its three cells.
    • A low cell surrounded by high ones. The 1 in the middle of the ring of 5s is not in the result: no search ever climbs to it from a lower cell.
    • Order of the result. Collecting the cells with the nested loops gives reading order with no sorting needed.

    Testing

    Results from running the solution:

    • The 5 by 5 grid of the first example: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
    • [[1]]: [[0, 0]]
    • [[5, 5, 5], [5, 1, 5], [5, 5, 5]]: [[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]]
    • [[1, 2, 3, 4]]: [[0, 0], [0, 1], [0, 2], [0, 3]]
    • [[4], [3], [2]]: [[0, 0], [1, 0], [2, 0]]
    • [[1, 2], [4, 3]]: [[0, 1], [1, 0], [1, 1]]
    • A 200 by 200 grid where every height is 7: 40,000 cells, returned quickly
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free