Pacific Atlantic Water Flow

You are given an m by n grid of heights. The Pacific Ocean touches the top and left edges; the Atlantic Ocean touches the bottom and right edges. Water flows from a cell to a neighbor (up, down, left, right) only if the neighbor’s height is less than or equal to the current cell. Return every cell from which water can reach both oceans.

Example#

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 includes cells like [0,4], [1,3], [2,2], [3,0], and [4,0], each of which can drain to both the Pacific and the Atlantic.

Brute force note#

Running a search from every cell to test if it reaches each ocean is O((m times n) squared), because each of m times n cells launches a full traversal. That is wasteful and repeats work.

Optimal approach#

Reverse the problem. Instead of asking which cells reach the ocean, ask which cells the ocean can reach flowing uphill. Start a traversal from all Pacific-edge cells, moving only to neighbors with height greater than or equal to the current cell, and mark every reachable cell. Do the same from all Atlantic-edge cells. The answer is the intersection: cells reachable in both passes.

 1def pacific_atlantic(heights):
 2    if not heights:
 3        return []
 4    rows, cols = len(heights), len(heights[0])
 5    pacific, atlantic = set(), set()
 6
 7    def dfs(r, c, visited, prev_height):
 8        if (r < 0 or r >= rows or c < 0 or c >= cols
 9                or (r, c) in visited or heights[r][c] < prev_height):
10            return
11        visited.add((r, c))
12        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
13            dfs(r + dr, c + dc, visited, heights[r][c])
14
15    for c in range(cols):
16        dfs(0, c, pacific, heights[0][c])
17        dfs(rows - 1, c, atlantic, heights[rows - 1][c])
18    for r in range(rows):
19        dfs(r, 0, pacific, heights[r][0])
20        dfs(r, cols - 1, atlantic, heights[r][cols - 1])
21
22    return [list(cell) for cell in pacific & atlantic]
23
24
25heights = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1],
26           [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]
27print(sorted(pacific_atlantic(heights)))

Complexity#

Time is O(m times n): each cell is visited at most once per ocean. Space is O(m times n) for the two visited sets and the recursion stack.

This multi-source traversal builds directly on the graphs topic page. Review it, then continue through the 60-day curriculum.