417. Pacific Atlantic Water FlowMedium

Analogy BFS Viz Brute Force Pitfalls Related

417. Pacific Atlantic Water Flow

MediumGraphBFSMulti-source·AmazonFacebook·⚡ Frequent

A rectangular island borders the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). heights[r][c] is the elevation. Water flows from a cell to an equal-or-lower neighbor. Find all cells from which water can flow to both oceans.

1 ≤ heights.length, heights[r].length ≤ 100
0 ≤ heights[r][c] ≤ 1000

Example

heights[[4,2,7,3,4],[7,4,6,4,7],[6,3,5,3,6]]

Output[[0,2],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4],[2,0]]

Real-world analogy: Watershed ridge-finding

🏔️ Continental Divide: Imagine a mountain range where rain can roll down to either the Pacific or the Atlantic. You want to find every peak (cell) that lies on a watershed ridge — high enough that rainwater from it could drain to either coast.

The clever reversal: Instead of checking each cell "can water from here reach the Pacific?", we ask: "starting from the Pacific shore and climbing uphill, which cells can we reach?" Any cell reachable from the Pacific shore (climbing ≥-height paths) is one that can drain down to the Pacific.

Run this twice — once from Pacific sources (top + left), once from Atlantic sources (bottom + right). The intersection = watershed ridge = answer.

Why reverse direction?

Forward: "can water from (r,c) reach the ocean?" requires a full DFS/BFS per cell → O((m·n)²). Reverse: start from the ocean border, climb uphill. Any reachable cell means water flows back down. Two multi-source BFS runs → O(m·n) total.

Algorithm — Multi-source BFS (reversed)

1. Seed Pacific BFS with all top-row + left-column cells.
2. BFS rule: from (r,c) go to neighbor (nr,nc) if heights[nr][nc] ≥ heights[r][c].
3. Mark all reachable cells in pac[][].
4. Repeat for Atlantic (bottom-row + right-column) → mark atl[][].
5. Return all (r,c) where pac[r][c] AND atl[r][c] are both true.

Approach	Time	Space	Notes
Brute Force (per-cell DFS)	O((m·n)²)	O(m·n)	TLE on large grids
Reverse Multi-source BFS ✓	O(m·n)	O(m·n)	Two passes, optimal

Visualizer — Reverse Multi-source BFS

■ Blue = Pacific reachable · ■ Red = Atlantic reachable · ■ Green = BOTH (answer) · Numbers = cell heights

PHASE:

—

REVERSE BFS—

Press ▶ or step forward to begin.

✓

—

SpacePlay/Pause ←→Step RReset F Fullscreen

Executing Code

def pacificAtlantic(self, heights):

    ROWS, COLS = len(heights), len(heights[0])

    dirs = [(1,0),(-1,0),(0,1),(0,-1)]

    pac = [[False]*COLS for _ in range(ROWS)]

    atl = [[False]*COLS for _ in range(ROWS)]

    def bfs(source, ocean):

        q = deque(source)

        while q:

            r, c = q.popleft(); ocean[r][c] = True

            for dr,dc in dirs:

                nr,nc = r+dr, c+dc

                if 0<=nr<ROWS and 0<=nc<COLS and not ocean[nr][nc]

                        and heights[nr][nc] >= heights[r][c]: q.append((nr,nc))

    pacific = [(0,c) for c in range(COLS)] + [(r,0) for r in range(ROWS)]

    atlantic= [(ROWS-1,c) for c in range(COLS)] + [(r,COLS-1) for r in range(ROWS)]

    bfs(pacific, pac); bfs(atlantic, atl)

    return [[r,c] for r in range(ROWS) for c in range(COLS) if pac[r][c] and atl[r][c]]

Brute Force — O((m·n)²)

For each cell, run a separate DFS checking if water can flow to both oceans. Correct but too slow for large grids.

brute_force.py

def pacificAtlantic(self, heights):
    ROWS, COLS = len(heights), len(heights[0])
    pacific = atlantic = False

    def dfs(r, c, prevVal):
        nonlocal pacific, atlantic
        if r < 0 or c < 0: pacific = True; return
        if r >= ROWS or c >= COLS: atlantic = True; return
        if heights[r][c] > prevVal: return
        tmp = heights[r][c]
        heights[r][c] = float('inf')    # mark visited
        for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]:
            dfs(r+dx, c+dy, tmp)
            if pacific and atlantic: break
        heights[r][c] = tmp             # restore

    res = []
    for r in range(ROWS):
        for c in range(COLS):
            pacific = atlantic = False
            dfs(r, c, float('inf'))
            if pacific and atlantic:
                res.append([r, c])
    return res  # O((m*n)^2) — TLE on large inputs

Common pitfalls

Wrong flow direction in BFS

In the reversed BFS, the condition is heights[nr][nc] ≥ heights[r][c] (climbing uphill/flat). Using ≤ instead gives the wrong direction — you'd be following downhill paths away from the ocean, not toward the interior.

Missing corner cells

Corner cells (e.g., (0,0) and (ROWS-1, COLS-1)) border two oceans each. The seeding loop handles them naturally — (0,0) is added by the top-row loop for Pacific; (ROWS-1,COLS-1) by the bottom-row loop for Atlantic. No special casing needed.

Running DFS/BFS from every cell separately

The brute force O((m·n)²) approach is too slow for 100×100 grids. Always use the reversed multi-source approach — two BFS runs total, not one per cell.

What to do next

Discussion

…

Loading comments…

LeetMotion