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.
Open on LeetCode ↗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.
Search upward from each ocean instead of downward from each cell. Reversing the flow condition to >= means one traversal per ocean marks everything that can drain into it, and the answer is the intersection of the two marked sets.
Approach
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).
Flood from the Atlantic border
Do the identical flood seeded from the bottom row and right column, into a separate visited set.
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.
Solution & live demo
Common pitfalls
Simulating downhill flow from every cell
for each cell: dfs downhill, check if it reaches both oceans
pacVis = bfs(pacific_border) atlVis = bfs(atlantic_border)
That's a separate search per cell — O((RC)²). Two searches from the borders answer the question for every cell at once, because reachability is symmetric under the reversed comparison.
Using > instead of >= when climbing
if heights[nr][nc] > heights[r][c]:
if heights[nr][nc] >= heights[r][c]:
Water flows to cells of equal or lower height, so climbing backwards must accept equal heights too. The strict version blocks every plateau and misses large regions.
Sharing one visited array between the two searches
vis = [[False]*C for _ in range(R)] # reused
def bfs(starts):
vis = [[False]*C for _ in range(R)]The two oceans' reachable sets overlap — that overlap is the answer. Sharing the array lets the first search block the second, and the intersection collapses to nothing.
Edge cases
The single cell touches both borders at once, so it always drains to both oceans.
Every cell reaches every border since >= holds everywhere; the whole grid qualifies.
They sit on both a Pacific and an Atlantic border edge simultaneously and are trivially in both sets.
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.