Start learning free

LESSON 483 OF 541 · GRAPHS

Pacific Atlantic Water Flow in Swift: 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: 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 array 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

    SWIFT · GRAPHS

    Pacific Atlantic Water Flow in Swift, explained

    Problem overview

    An island is a grid of cells, given as heights, an array of rows of integers. The Pacific Ocean touches the left and top edges, and the Atlantic Ocean touches the right and bottom edges. Rain falls on every cell. Water flows from a cell to an up, down, left or right neighbor 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 pacificAtlantic 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 within a row.

    For the 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

    the answer is [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]. The cell [0, 4] touches both the top edge and the right edge. From [2, 2], with height 5, water runs up to the Pacific through [1, 2] and [0, 2], and right to the Atlantic through [2, 3] and [2, 4]. A single cell, [[1]], touches all four edges and returns [[0, 0]].

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

    Approach: climb up from each ocean

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

    Turn the question around. Start at an ocean and climb. A cell at the edge sends its water straight into the ocean. A neighbor can send its water to the ocean through that cell when the neighbor is at least as high, because water moves down or level. So a breadth-first search that starts from all the edge cells of one ocean at once, and moves to a neighbor only when it is at least as high, reaches exactly the cells whose water can flow to that ocean.

    Run it twice: once from the top row and left column (Pacific), once from the bottom row and right column (Atlantic). A cell belongs to the answer when both searches reached it. Each search visits every cell at most once.

    For the grid above, the Pacific search marks these cells (#) and the Atlantic search marks these:

    pacific          atlantic
# # # # #        . . . . #
# # # # #        . . . # #
# # # . .        . . # # #
# # . . .        # # # # #
# . . . .        # # # # #

    The cells marked in both are the seven in the answer.

    Step by step

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

    1. Store the size: rows is heights.count and cols is heights[0].count. Every row has the same length.
    2. Find the Pacific cells: reach(heights, 0, 0) goes into pacific. The helper takes an edge row and an edge column. The Pacific touches row 0 and column 0.
    3. Find the Atlantic cells: reach(heights, rows - 1, cols - 1) goes into atlantic. One helper serves both oceans.
    4. Create result as an empty [[Int]].
    5. Loop r over 0..<rows. Row by row, then left to right, is the order the answer needs.
    6. Loop c over 0..<cols.
    7. If pacific[r][c] and atlantic[r][c] are both true, append [r, c].
    8. Return result.
    9. Write reach with parameters _ heights: [[Int]], _ edgeRow: Int, _ edgeCol: Int, returning a [[Bool]].
    10. Store the size again. The variables in pacificAtlantic aren't visible in the helper.
    11. Create seen, rows arrays of cols false values. It becomes true for every cell the search reaches.
    12. Create queue as an empty array of (Int, Int) tuples, each one a row and a column.
    13. Loop over the rows,
    14. and over the columns. The search starts from every edge cell at once.
    15. Check r == edgeRow || c == edgeCol. Such a cell touches the ocean.
    16. Mark it and queue it: seen[r][c] = true and append (r, c). A cell is marked when it joins the queue, so none joins twice.
    17. Define directions as (-1, 0), (1, 0), (0, -1), (0, 1): up, down, left, right. Diagonal cells aren't neighbors.
    18. Create head at 0, the index of the next queued cell. This avoids removeFirst(), which shifts every remaining element.
    19. Loop while head < queue.count. Each cell is queued at most once, so this runs at most m · n times.
    20. Unpack the tuple at head with let (row, col) = queue[head].
    21. Add 1 to head.
    22. Loop over directions as (dr, dc).
    23. Compute nextRow and nextCol.
    24. Check the neighbor is inside the grid before using it as an index.
    25. Check it can be climbed to: not seen yet, and heights[nextRow][nextCol] >= heights[row][col]. This is the key line: the search walks against the flow.
    26. Mark and queue the neighbor.
    27. Return seen.

    The solution in Swift

    class Solution {
    func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
        let rows = heights.count
        let cols = heights[0].count
        let pacific = reach(heights, 0, 0)
        let atlantic = reach(heights, rows - 1, cols - 1)
        var result = [[Int]]()
        for r in 0..<rows {
            for c in 0..<cols {
                if pacific[r][c] && atlantic[r][c] {
                    result.append([r, c])
                }
            }
        }
        return result
    }
    func reach(_ heights: [[Int]], _ edgeRow: Int, _ edgeCol: Int) -> [[Bool]] {
        let rows = heights.count
        let cols = heights[0].count
        var seen = [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows)
        var queue = [(Int, Int)]()
        for r in 0..<rows {
            for c in 0..<cols {
                if r == edgeRow || c == edgeCol {
                    seen[r][c] = true
                    queue.append((r, c))
                }
            }
        }
        let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        var head = 0
        while head < queue.count {
            let (row, col) = queue[head]
            head += 1
            for (dr, dc) in directions {
                let nextRow = row + dr
                let 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.append((nextRow, nextCol))
                    }
                }
            }
        }
        return seen
    }
}

    The Swift details worth a closer look:

    • Nested arrays are values. [[Bool]](repeating: [Bool](repeating: false, count: cols), count: rows) repeats the same row value, but arrays are copied when changed, so seen[r][c] = true changes only that cell.
    • Tuples. (Int, Int) keeps a row and a column together. let (row, col) = queue[head] and for (dr, dc) in directions unpack tuples into separate constants.
    • Type inference. [(-1, 0), (1, 0), (0, -1), (0, 1)] is inferred as [(Int, Int)], so no annotation is needed.
    • Short-circuit checks. In the bounds test, && stops at the first false. Only after all four bounds hold does the next if use the indexes. An out-of-range index would trap and crash the program.
    • Methods calling methods. reach belongs to the same class, so pacificAtlantic calls it by name.

    Complexity

    Time: O(m · n). Each search marks a cell once when it is queued, so it handles at most m · n cells, with four neighbor checks each. Two searches and one pass over the grid for the answer stay within O(m · n).

    Space: O(m · n). Each search has a seen grid and a queue of up to m · n cells, and the two grids are kept together.

    Edge cases and common mistakes

    • Single cell. [[1]] gives [[0, 0]], since the cell is on every edge.
    • Equal heights. Water flows between cells of equal height, so the comparison is >=. In [[5, 5, 5], [5, 1, 5], [5, 5, 5]] all eight 5s are in the answer, and the 1 in the middle is not. With a strict >, only 2 of the 9 cells would pass.
    • Direction. The search climbs, so it moves to a neighbor that is at least as high, not at most as high. Reversing the comparison answers a different question.
    • One row or one column. [[1, 2, 3]] gives all three cells, because each is on both a Pacific and an Atlantic edge. [[3], [2], [1]] does the same.
    • Flat grids. [[1, 1], [1, 1]] returns all four cells.
    • Result order. The answer is built by scanning rows then columns, which is already in reading order, so no sorting is needed.
    • Marking late. Marking a cell when it leaves the queue instead of when it joins lets it be queued several times.

    Testing

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