Reasoning Into CodeArunank Divya Sharan · Python edition← Arunank’s portfolio
Module 14 · Grid DFS, BFS, and Multi-Source Search

140. Pacific Atlantic Water Flow

Interview · Download this solution · All solutions and shared helpers

Problem

Given a rectangular height matrix, return all cells from which water can reach both oceans. The Pacific touches the top and left borders; the Atlantic touches the bottom and right borders. Water moves to four-neighbor cells of equal or lower height. Return [row,column] pairs in row-major order; input is unchanged.

Examples

Example 1

pacific_atlantic([[1,2],[4,3]])
=> [[0, 1], [1, 0], [1, 1]]

Only the lowest top-left cell cannot drain to the Atlantic.

Example 2

pacific_atlantic([[7]])
=> [[0, 0]]

The singleton touches both oceans.

Example 3

pacific_atlantic([])
=> []

No cell reaches either ocean.

Reveal the worked solution and reasoning

Why this mechanism works

Searching downhill from every cell repeats paths. Reverse the flow: start from each ocean's borders and move uphill or level. A reverse-reachable cell has a valid downhill path to that ocean. Intersect the two reverse-reachability sets.

State and boundaries

Each reachable set contains cells that can drain to its seeded ocean. Reverse traversal accepts a neighbor only when its height is >= the current height.

Protocol

  1. Seed Pacific border cells and traverse reverse flow.
  2. Independently seed Atlantic borders and traverse reverse flow.
  3. Scan cells in row-major order.
  4. Emit those in both reached sets.

Visualization

forward water: high -> low -> ocean
reverse search: ocean -> low -> high
answer = Pacific-reachable AND Atlantic-reachable

Python implementation

from collections import deque

def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []
    rows, cols = len(heights), len(heights[0])
    def reachable(starts):
        seen = set(starts)
        queue = deque(seen)
        while queue:
            r, c = queue.popleft()
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                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 = reachable([(0,c) for c in range(cols)] + [(r,0) for r in range(rows)])
    atlantic = reachable([(rows-1,c) for c in range(cols)]
                         + [(r,cols-1) for r in range(rows)])
    return [[r,c] for r in range(rows) for c in range(cols)
            if (r,c) in pacific and (r,c) in atlantic]

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

pacific_atlantic([[1,2],[4,3]])

L4 pacific_atlantic: if not heights or not heights[0]:
heights=[[1, 2], [4, 3]]

L6 pacific_atlantic: rows, cols = len(heights), len(heights[0])
heights=[[1, 2], [4, 3]]; cols=2; rows=2

L19 pacific_atlantic: pacific = reachable([(0,c) for c in range(cols)] + [(r,0) for r in range(rows)])
heights=[[1, 2], [4, 3]]; cols=2; rows=2; c=0

L19 pacific_atlantic: pacific = reachable([(0,c) for c in range(cols)] + [(r,0) for r in range(rows)])
heights=[[1, 2], [4, 3]]; cols=2; rows=2; c=1

L19 pacific_atlantic: pacific = reachable([(0,c) for c in range(cols)] + [(r,0) for r in range(rows)])
heights=[[1, 2], [4, 3]]; cols=2; rows=2; r=0

L19 pacific_atlantic: pacific = reachable([(0,c) for c in range(cols)] + [(r,0) for r in range(rows)])
heights=[[1, 2], [4, 3]]; cols=2; rows=2; r=1

L8 reachable: seen = set(starts)
starts=[(0, 0), (0, 1), (0, 0), (1, 0)]; seen={(0, 0), (0, 1), (1, 0)}; cols=2; heights=[[1, 2], [4, 3]]; rows=2

L9 reachable: queue = deque(seen)
starts=[(0, 0), (0, 1), (0, 0), (1, 0)]; seen={(0, 0), (0, 1), (1, 0)}; cols=2; heights=[[1, 2], [4, 3]]; rows=2; queue=deque([(0, 1), (1, 0), (0, 0)])

... 76 intermediate state changes omitted ...

L22 pacific_atlantic: return [[r,c] for r in range(rows) for c in range(cols)
heights=[[1, 2], [4, 3]]; cols=2; rows=2; pacific={(0, 0), (0, 1), (1, 0), (1, 1)}; atlantic={(0, 1), (1, 0), (1, 1)}; c=1; r=0

L22 pacific_atlantic: return [[r,c] for r in range(rows) for c in range(cols)
heights=[[1, 2], [4, 3]]; cols=2; rows=2; pacific={(0, 0), (0, 1), (1, 0), (1, 1)}; atlantic={(0, 1), (1, 0), (1, 1)}; c=0; r=1

L22 pacific_atlantic: return [[r,c] for r in range(rows) for c in range(cols)
heights=[[1, 2], [4, 3]]; cols=2; rows=2; pacific={(0, 0), (0, 1), (1, 0), (1, 1)}; atlantic={(0, 1), (1, 0), (1, 1)}; c=1; r=1

L22 pacific_atlantic: return [[r,c] for r in range(rows) for c in range(cols)
heights=[[1, 2], [4, 3]]; cols=2; rows=2; pacific={(0, 0), (0, 1), (1, 0), (1, 1)}; atlantic={(0, 1), (1, 0), (1, 1)}

Result: [[0, 1], [1, 0], [1, 1]]. Only the lowest top-left cell cannot drain to the Atlantic.

pacific_atlantic([[7]])

L4 pacific_atlantic: if not heights or not heights[0]:
heights=[[7]]

L6 pacific_atlantic: rows, cols = len(heights), len(heights[0])
heights=[[7]]; cols=1; rows=1

L19 pacific_atlantic: pacific = reachable([(0,c) for c in range(cols)] + [(r,0) for r in range(rows)])
heights=[[7]]; cols=1; rows=1; c=0

L19 pacific_atlantic: pacific = reachable([(0,c) for c in range(cols)] + [(r,0) for r in range(rows)])
heights=[[7]]; cols=1; rows=1; r=0

L8 reachable: seen = set(starts)
starts=[(0, 0), (0, 0)]; seen={(0, 0)}; cols=1; heights=[[7]]; rows=1

L9 reachable: queue = deque(seen)
starts=[(0, 0), (0, 0)]; seen={(0, 0)}; cols=1; heights=[[7]]; rows=1; queue=deque([(0, 0)])

L11 reachable: r, c = queue.popleft()
starts=[(0, 0), (0, 0)]; seen={(0, 0)}; cols=1; heights=[[7]]; rows=1; queue=deque([]); r=0; c=0

L12 reachable: for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
starts=[(0, 0), (0, 0)]; seen={(0, 0)}; cols=1; heights=[[7]]; rows=1; queue=deque([]); r=0; c=0; dr=1; dc=0

... 22 intermediate state changes omitted ...

L13 reachable: nr, nc = r + dr, c + dc
starts=[(0, 0), (0, 0)]; seen={(0, 0)}; cols=1; heights=[[7]]; rows=1; queue=deque([]); r=0; c=0; dr=0; dc=-1; nr=0; nc=-1

L20 pacific_atlantic: atlantic = reachable([(rows-1,c) for c in range(cols)]
heights=[[7]]; cols=1; rows=1; pacific={(0, 0)}; atlantic={(0, 0)}

L22 pacific_atlantic: return [[r,c] for r in range(rows) for c in range(cols)
heights=[[7]]; cols=1; rows=1; pacific={(0, 0)}; atlantic={(0, 0)}; c=0; r=0

L22 pacific_atlantic: return [[r,c] for r in range(rows) for c in range(cols)
heights=[[7]]; cols=1; rows=1; pacific={(0, 0)}; atlantic={(0, 0)}

Result: [[0, 0]]. The singleton touches both oceans.

Why the solution is correct

Reversing each downhill edge creates exactly the uphill-or-level traversal rule. Thus a cell is reached from an ocean border precisely when a forward water path exists from it to that ocean. Membership in both sets is equivalent to reaching both oceans.

Time and space

O(R*C) time and O(R*C) auxiliary space for two traversals and their reached sets.

Common mistakes

Using downhill movement from the ocean computes the wrong relation. Requiring strictly greater height incorrectly blocks level plateaus.

Reasoning card

State: Each reachable set contains cells that can drain to its seeded ocean. Reverse traversal accepts a neighbor only when its height is >= the current height.

Invariant: Each visited set contains cells capable of reaching that ocean.

Decision to rehearse: Reverse the flow: start from oceans and traverse uphill/reverse-valid edges.

Finish: Emit those in both reached sets

Transfer exercise

Generalize the intersection to three destination regions and decide whether to keep separate sets or a bitmask per cell.