Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Pacific Atlantic Water Flow

LeetCode #417Medium
Flood inward from both oceans, intersect

Given a grid of cell heights where the Pacific Ocean borders the top and left edges and the Atlantic borders the bottom and right edges, return all cells from which water can flow to both oceans, moving only to equal-or-lower neighboring cells.

Asked atAmazonGoogle
step 1 / 39
5 × 5 heights · flow to ≤ neighbour
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
Reverse DFS from both oceans
▸
1flood(r, c, reach):
2    reach[r][c] = true
3    for each neighbour with height >= heights[r][c]:
4        if not reach[nr][nc]: flood(nr, nc, reach)
5seed Pacific from top row + left col
6seed Atlantic from bottom row + right col
7// intersect
8answer = cells where pacific && atlantic
9return answer
state
  • ruleflow to ≤ neighbour
  • trickreverse from oceans

line 1Water on each cell flows to neighbours of EQUAL-or-LOWER height. We want every cell whose water can reach BOTH the Pacific (top & left edges) and the Atlantic (bottom & right edges). Testing each cell forward is expensive, so we REVERSE the flow: start at an ocean border and climb INWARD to cells that are ≥ the current height (water could have flowed down to us from them).