Problem Statement
Pacific Atlantic Water Flow
You are given a grid of numbers. Each number is the height of one square of land on an island. The island sits between two oceans. The Pacific Ocean touches the top edge and the left edge. The Atlantic Ocean touches the bottom edge and the right edge. When it rains, water on a square can flow to a neighbor (up, down, left, or right) only if that neighbor is the same height or lower, because water rolls downhill. Your job is to find every square from which water can reach both oceans, and return their coordinates.
Signals to notice
Brute force first
For each cell, DFS/BFS to check if water can reach both oceans. Each cell's reachability is computed independently. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
The key insight
Reverse thinking: start from ocean borders and flow uphill. DFS/BFS from Pacific border marks all cells that can reach Pacific. Same from Atlantic border. Intersection of both sets is the answer. The goal is not to be clever for its own sake, but to remember the one relationship that keeps the solution grounded as you move forward.
Trace it on heights=[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] (m=5,n=5)
Pacific seeds = top row + left col: {(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(2,0),(3,0),(4,0)} — every border cell touching the Pacific (top/left).
Pacific BFS flows uphill (visit neighbor only if heights[neighbor] >= heights[current]); e.g. (1,3)->(1,4) since 4>=4. pac = {(0,0),(0,1),(0,2),(0,3),(0,4),(1,0),(1,1),(1,2),(1,3),(1,4),(2,0),(2,1),(2,2),(3,0),(3,1),(4,0)} (16 cells).
Atlantic seeds = bottom row + right col: {(4,0),(4,1),(4,2),(4,3),(4,4),(0,4),(1,4),(2,4),(3,4)} — every border cell touching the Atlantic.
Atlantic BFS flows uphill -> atl = {(0,4),(1,3),(1,4),(2,2),(2,3),(2,4),(3,0),(3,1),(3,2),(3,3),(3,4),(4,0),(4,1),(4,2),(4,3),(4,4)} (16 cells).
Intersect pac & atl: cells in BOTH sets = {(0,4),(1,3),(1,4),(2,2),(3,0),(3,1),(4,0)}.
Return list(pac & atl) = [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].What must stay true
Instead of asking 'can this cell reach the ocean?' (flows downhill), ask 'can the ocean reach this cell?' (flows uphill from the border). The answer is the same, but starting from borders is much more efficient. If that remains true after every update, the rest of the reasoning has a stable place to stand.
Shape of the loop
function bfs(starts): # border cells touching one ocean
visited = set(starts); queue = starts
while queue:
r,c = pop(queue)
for each 4-neighbor (nr,nc):
if in-bounds and not visited and heights[nr][nc] >= heights[r][c]:
visited.add((nr,nc)); push(queue,(nr,nc)) # flow UPHILL
return visited
# pac = bfs(top row + left col); atl = bfs(bottom row + right col)
return list( bfs(pacific_border) & bfs(atlantic_border) )Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Flowing downhill from each cell — that's the natural direction but leads to worst case. Reversing to flow uphill from the borders reduces it to two passes. The fix is usually to return to the meaning of each move, not just the steps themselves.