Pacific Atlantic Water Flow: Reverse Multi-Source BFS from Both Oceans

Problem

A rectangular island is described by a grid of heights. The Pacific Ocean touches the top and left edges and the Atlantic Ocean touches the bottom and right edges. Rain on a cell flows to a neighbouring cell (up, down, left or right) whose height is less than or equal to its own, and from an edge cell straight into the ocean on that side. Return every cell from which water can reach both oceans.

This is widely known as LeetCode 417, “Pacific Atlantic Water Flow”.

Assume up to 200 by 200 cells with non-negative heights.

Examples

heights:
  3 3 4
  2 5 1
  4 2 3

Pacific edges: row 0 and column 0.  Atlantic edges: row 2 and column 2.
Cells reaching both: (0,2), (1,1), (2,0)
  (0,2): top row (Pacific), right column (Atlantic)
  (1,1): height 5 flows up to (0,1)=3 (Pacific) and right to (1,2)=1 (Atlantic)
  (2,0): left column (Pacific), bottom row (Atlantic)
(0,0) reaches only the Pacific: its neighbours 3 and 2 lead nowhere towards the Atlantic.

Approach 1: search from every cell

For each cell, run a downhill search and record which oceans it reaches.

def pacific_atlantic_brute(heights):
    if not heights or not heights[0]:
        return []
    rows, cols = len(heights), len(heights[0])
    result = []
    for sr in range(rows):
        for sc in range(cols):
            pacific = atlantic = False
            seen, stack = {(sr, sc)}, [(sr, sc)]
            while stack:
                r, c = stack.pop()
                if r == 0 or c == 0:
                    pacific = True
                if r == rows - 1 or c == cols - 1:
                    atlantic = True
                for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                    if (0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen
                            and heights[nr][nc] <= heights[r][c]):
                        seen.add((nr, nc))
                        stack.append((nr, nc))
            if pacific and atlantic:
                result.append([sr, sc])
    return result

Each search can visit the whole grid, so this is O((R * C)^2).

Approach 2: optimal, reverse multi-source BFS

Idea

Instead of asking “where does water from this cell go”, ask “which cells can drain into this ocean”. Water flows from high to low or equal, so in reverse you climb: from a cell you may move to a neighbour that is at least as high. A multi-source BFS starts with all edge cells of one ocean in the queue at once.

Template

bfs(sources):
    visited = set(sources); queue = sources
    while queue:
        cell = queue.pop_front()
        for nb in 4 neighbours:
            if nb inside, not visited and height[nb] >= height[cell]:
                visited.add(nb); queue.append(nb)
    return visited

answer = bfs(pacific edges) ∩ bfs(atlantic edges)

Python solution

from collections import deque

def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []
    rows, cols = len(heights), len(heights[0])

    def climb(sources):
        seen = set(sources)
        queue = deque(sources)
        while queue:
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if (0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen
                        and heights[nr][nc] >= heights[r][c]):
                    seen.add((nr, nc))
                    queue.append((nr, nc))
        return seen

    pacific = climb([(0, c) for c in range(cols)] + [(r, 0) for r in range(1, rows)])
    atlantic = climb([(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows - 1)])
    return sorted([r, c] for r, c in pacific & atlantic)

Complexity

• Time: O(R * C). Each search visits each cell once and checks four neighbours.
• Space: O(R * C) for the two visited sets and the queue.

Tests

h = [[3, 3, 4],
     [2, 5, 1],
     [4, 2, 3]]

for fn in (pacific_atlantic, pacific_atlantic_brute):
    assert sorted(fn(h)) == [[0, 2], [1, 1], [2, 0]]
    assert fn([]) == [] and fn([[]]) == []                    # empty
    assert fn([[7]]) == [[0, 0]]                              # single cell touches both
    assert sorted(fn([[1, 1], [1, 1]])) == [[0, 0], [0, 1], [1, 0], [1, 1]]   # flat: all
    assert sorted(fn([[1, 2, 3]])) == [[0, 0], [0, 1], [0, 2]]               # one row touches both

# Agreement on a random grid
import random
random.seed(3)
for _ in range(20):
    g = [[random.randint(0, 5) for _ in range(5)] for _ in range(4)]
    assert sorted(pacific_atlantic(g)) == sorted(pacific_atlantic_brute(g))

Edge cases and pitfalls

• Wrong comparison in reverse. Climbing uses >=; using <= repeats the forward search from the coast and gives nonsense.
• Strict versus non-strict. Water flows onto equal heights, so flat regions must be included (>=, not >).
• Corners. The top-right and bottom-left corners touch both oceans; including them in both source lists is required, and the code above does so through the full rows.
• Single row or column. Every cell touches both oceans.

Where this shows up in data engineering

Reverse traversal is how data lineage answers impact questions: rather than tracing every source forward, start from the affected output (or the set of outputs) and walk upstream once. Multi-source BFS is the same trick as seeding a lineage query with every table owned by one team.