Start learning free

LESSON 478 OF 536 · GRAPHS

Pacific Atlantic Water Flow in Python: Two BFS from the Edges

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: a list of rows, where each row is a list 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

    PYTHON · GRAPHS

    Pacific Atlantic Water Flow in Python, explained

    Problem overview

    A rectangular island is a grid of square cells with m rows and n columns. The list heights holds one list per row, and heights[r][c] is the height of the cell in row r and column c. The Pacific Ocean touches the top and left edges. The Atlantic Ocean touches the bottom and right edges.

    Rain falls on every cell. Water flows from a cell to a neighbor (up, down, left or right) when the neighbor's height is less than or equal to the cell's height, and from any edge cell into the ocean that touches that edge. The method pacificAtlantic returns the cells whose 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 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]] the answer is [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]. The cell [0, 4] touches the top edge and the right edge, so it reaches both oceans directly. The cell [2, 2], with height 5, reaches the Pacific through [1, 2] and [0, 2], and the Atlantic through [2, 3] and [2, 4]. The cell [2, 1], with height 4, reaches the Pacific through [2, 0], but every path to the Atlantic needs a step up.

    For [[1]] the answer is [[0, 0]], since the one cell touches all four edges. For a ring of 5s around a 1, all the 5s qualify, because water moves between equal heights, and the 1 in the middle does not: it is lower than all its neighbors.

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

    Approach: climb up from the oceans

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

    Turn the question around. Instead of asking where a cell's water goes, ask which cells can send water to the Pacific. Start at the cells along the Pacific's edges, which reach it directly, and walk against the flow: move to a neighbor only when it is at least as high as the current cell. Water from that neighbor can flow down, or level, into the current cell, and from there to the ocean along the path already found. Every cell this 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 reached. Each search is a breadth-first search that starts from all its edge cells at once and visits every cell at most once.

    For the first example, the two searches mark these cells (# means reached):

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

    The cells marked in both grids are exactly the seven in the answer: [0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1] and [4, 0].

    Step by step

    The main method comes first, and then the helper reach that both oceans share.

    1. Store the grid's size: rows = len(heights) and cols = len(heights[0]). Every row has the same length.
    2. Find the Pacific cells with self.reach(heights, 0, 0). The Pacific touches row 0 and column 0. The helper returns a grid of booleans, which the lesson writes after this method.
    3. Find the Atlantic cells with self.reach(heights, rows - 1, cols - 1). Only the edges differ.
    4. Create an empty result list.
    5. Loop over r in range(rows), and inside it over c in range(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 [r, c] to result.
    7. Return result.
    8. Write reach, a method taking self, heights, edgeRow and edgeCol. It returns a grid of booleans marking the cells whose water can reach the ocean at that row and column.
    9. Store rows and cols again. The variables of the main method aren't visible here.
    10. Create seen as a grid of False values with a list comprehension. seen[r][c] becomes True once the search has reached the cell.
    11. Create an empty deque named queue. It holds the cells that were reached but not yet looked around from, as (row, column) tuples.
    12. Loop over every cell and, when r == edgeRow or c == edgeCol, the cell touches the ocean. Set seen[r][c] to True and append (r, c) to queue. A cell is marked when it joins the queue, so no cell joins twice.
    13. Create directions, the four moves as tuples: (-1, 0), (1, 0), (0, -1) and (0, 1). Diagonal cells aren't neighbors.
    14. Loop while queue is not empty. Each cell joins the queue at most once, so the loop runs at most m · n times.
    15. Take the front cell with popleft() and unpack it into row and col.
    16. Loop over directions as dr, dc, and compute nextRow = row + dr and nextCol = col + dc.
    17. Check that the neighbor is inside the grid: 0 <= nextRow < rows and 0 <= nextCol < cols.
    18. Check that the search can climb there: the neighbor isn't seen yet, and heights[nextRow][nextCol] >= heights[row][col]. This is the key line: it walks against the flow.
    19. Mark the neighbor as seen and append (nextRow, nextCol) to queue.
    20. Return seen after the loop.

    The solution in Python

    class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        rows = len(heights)
        cols = len(heights[0])
        pacific = self.reach(heights, 0, 0)
        atlantic = self.reach(heights, rows - 1, cols - 1)
        result = []
        for r in range(rows):
            for c in range(cols):
                if pacific[r][c] and atlantic[r][c]:
                    result.append([r, c])
        return result

    def reach(self, heights: List[List[int]], edgeRow: int, edgeCol: int) -> List[List[bool]]:
        rows = len(heights)
        cols = len(heights[0])
        seen = [[False] * cols for _ in range(rows)]
        queue = deque()
        for r in range(rows):
            for c in range(cols):
                if r == edgeRow or c == edgeCol:
                    seen[r][c] = True
                    queue.append((r, c))
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        while queue:
            row, col = queue.popleft()
            for dr, dc in directions:
                nextRow = row + dr
                nextCol = col + dc
                if 0 <= nextRow < rows and 0 <= nextCol < cols:
                    if not seen[nextRow][nextCol] and heights[nextRow][nextCol] >= heights[row][col]:
                        seen[nextRow][nextCol] = True
                        queue.append((nextRow, nextCol))
        return seen

    Python details worth a closer look:

    • Building the grid. [[False] * cols for _ in range(rows)] makes a separate row list for each row. [[False] * cols] * rows would repeat one row object: after s = [[False] * 3] * 2 and s[0][1] = True, s is [[False, True, False], [False, True, False]], and marking one cell marks a whole column. With the comprehension, the same assignment leaves [[False, True, False], [False, False, False]].
    • The chained comparison 0 <= nextRow < rows checks both bounds at once. The check matters because a negative index doesn't fail in Python. l[-1] reads the last element, so an unchecked nextRow of -1 would silently read the bottom row.
    • Tuples in the queue. (r, c) is a tuple, and row, col = queue.popleft() unpacks it into two variables. The same unpacking reads each move in for dr, dc in directions.
    • deque. popleft() takes constant time, unlike list.pop(0). The lesson's editor already provides deque. In a file of your own, add from collections import deque.
    • Lists of booleans can be used directly in if. pacific[r][c] and atlantic[r][c] needs no == True.

    Complexity

    Time: O(m · n). Each of the two searches marks a cell once and queues it once, and it looks at four neighbors per cell, which is a constant. Building the result reads each cell once more.

    Space: O(m · n). Each seen grid has m · n entries, and the queue holds at most that many cells.

    Edge cases and common mistakes

    • The wrong direction of the comparison. The search climbs, so it moves to a neighbor that is at least as high. Using <= would follow the water instead, and from the edge cells it would find the wrong cells.
    • Strict instead of non-strict. With > instead of >=, level paths are cut. For a ring of 5s around a 1, the answer would shrink to [[0, 2], [2, 0]].
    • Only the corners. Every cell on an edge row or column touches the ocean, not only the corner cell. That is why the start loop tests r == edgeRow or c == edgeCol.
    • A one-row or one-column grid. [[1, 2, 3]] gives [[0, 0], [0, 1], [0, 2]]: every cell touches both oceans. A single column [[3], [2], [1]] works the same way.
    • A shared row object in the grid. It makes the marks leak between rows, as shown above.
    • Reading order. The answer is built by scanning rows and columns, so it is in reading order without any sorting.

    Testing

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