LeetCode #417 Medium

Pacific Atlantic Water Flow

Given a height grid where water flows to equal-or-lower neighbors, find every cell that can drain to both the Pacific (top/left) and Atlantic (bottom/right) oceans.

bfsgridreverse-search

Open on LeetCode ↗

02

Intuition

💡

The natural instinct is to start a search from each individual cell and ask whether water flowing downhill from it can reach both oceans - that means running a full search per cell. Reverse the question instead: start AT each ocean's border and walk UPHILL, to neighbors whose height is greater than or equal to the current cell. That correctly answers 'which cells could send water down to this ocean', because uphill-reachability from the border is the mirror image of downhill-flow into it. Do this once for the Pacific border and once for the Atlantic border, and the answer is simply the intersection of the two reachable sets.

03

Approach

1

Flood from the Pacific border

Seed a BFS/DFS with every cell touching the top row or left column. From each cell, move to a neighbor only if its height is >= the current cell's height (walking uphill, the reverse of water flowing down).

2

Flood from the Atlantic border

Do the identical flood seeded from the bottom row and right column, into a separate visited set.

3

Intersect the two sets

A cell can drain to both oceans exactly when it is marked reachable by both floods, so the final answer is every cell present in both visited sets.

04

Solution & live demo

python

▶1class Solution:
▶2    def pacificAtlantic(self, heights):
▶3        if not heights or not heights[0]:
▶4            return []
▶5        R, C = len(heights), len(heights[0])
▶6        def bfs(starts):
▶7            from collections import deque
▶8            vis = [[False]*C for _ in range(R)]
▶9            q = deque(starts)
▶10            for r, c in starts:
▶11                vis[r][c] = True
▶12            while q:
▶13                r, c = q.popleft()
▶14                for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
▶15                    if 0<=nr<R and 0<=nc<C and not vis[nr][nc] and heights[nr][nc] >= heights[r][c]:
▶16                        vis[nr][nc] = True
▶17                        q.append((nr, nc))
▶18            return vis
▶19        pac = [(r,0) for r in range(R)] + [(0,c) for c in range(C)]
▶20        atl = [(r,C-1) for r in range(R)] + [(R-1,c) for c in range(C)]
▶21        pacVis = bfs(pac)
▶22        atlVis = bfs(atl)
▶23        return [[r,c] for r in range(R) for c in range(C) if pacVis[r][c] and atlVis[r][c]]

05

Edge cases

1x1 grid

The single cell touches both borders at once, so it always drains to both oceans.

Flat grid (all equal heights)

Every cell reaches every border since >= holds everywhere; the whole grid qualifies.

Corner cells

They sit on both a Pacific and an Atlantic border edge simultaneously and are trivially in both sets.

Isolated high peak inland

Uphill walk from both borders can still reach it if there's a nondecreasing path; if not, it's excluded from one or both sets.

06

Complexity

Time

O(R*C)

Space

O(R*C)

Two independent BFS floods instead of a search launched from every cell.