Pacific Atlantic Water Flow

Pacific Atlantic Water Flow looks like a maze problem, but its real lesson is a classic interview move: when "from every cell, can I reach the goal?" is expensive, flip the search and start from the goal instead.

3 3 3
3 1 4
2 4 5

The slow way first

The literal reading: for each of the m × n cells, run a flood-fill downhill and see whether it can dribble all the way to a Pacific edge, then do it again for the Atlantic. That is a full grid traversal per starting cell — roughly O((m·n)²). Far too slow.

The question to ask: what am I re-computing? The same downhill paths, over and over, from different starts. There is a much cheaper framing hiding here.

The idea: search uphill from each ocean

Reverse the flow. If water can run downhill from cell A to the ocean, then standing at the ocean we can walk uphill back to A. So start at the ocean border and do one flood-fill that climbs to neighbors of equal or greater height. Every cell that fill touches can drain to that ocean.

Run that flood-fill once per ocean — seeding from the Pacific border, then from the Atlantic border — and you get two reachable sets. The answer is their intersection.

The key insight: searching from the oceans visits each cell a constant number of times total, turning O((m·n)²) into O(m·n).

Walk through it

Step through the animation. First the Pacific search seeds the top row and left column, then climbs uphill — reaching everything except the center pit. The Atlantic search does the same from the opposite corner. Overlay the two sets and every cell except the lone 1 is reachable from both.

Pseudocode

make two empty sets: pacific, atlantic
define climb(r, c, seen, prev):
    if (r,c) already in seen, or this cell is LOWER than prev: stop
    add (r,c) to seen
    for each of the 4 neighbors in bounds:
        climb(neighbor, seen, height of this cell)   # uphill: prev = my height
seed climb from every Pacific border cell into "pacific"
seed climb from every Atlantic border cell into "atlantic"
return every cell that is in BOTH sets

The Python solution

def pacific_atlantic(heights):
    rows, cols = len(heights), len(heights[0])
    pac, atl = set(), set()
 
    def dfs(r, c, seen, prev):
        if (r, c) in seen or heights[r][c] < prev:
            return
        seen.add((r, c))
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            if 0 <= r+dr < rows and 0 <= c+dc < cols:
                dfs(r+dr, c+dc, seen, heights[r][c])
 
    for c in range(cols):
        dfs(0, c, pac, 0); dfs(rows-1, c, atl, 0)
    for r in range(rows):
        dfs(r, 0, pac, 0); dfs(r, cols-1, atl, 0)
    return [list(p) for p in pac & atl]

• pac and atl are the sets of coordinates reachable from each ocean.
• dfs climbs uphill: it stops if it has seen the cell, or if the cell is lower than prev (the height it just came from) — that is the reversed flow rule.
• When we recurse we pass heights[r][c] as the new prev, so the next cell must be at least this tall.
• The two loops seed the search from every border cell: top/bottom rows for the columns, left/right columns for the rows.
• pac & atl is Python set intersection — exactly the cells that drain to both oceans.

Complexity

We visit each cell a bounded number of times across both floods, so the work is linear in the grid size. The space is the two visited sets plus the recursion stack, all O(m·n).

When this pattern shows up

Practice