Pacific Atlantic Water Flow

Medium#417grid

You get a grid of heights, an island between two oceans: the Pacific washes its top and left edges, the Atlantic its bottom and right ones. Rain runs from a cell to a side neighbour that is no higher, and from an edge cell into the ocean there. List the cells whose water can reach both oceans. Our heights: 1 2 3, 4 5 2, 3 1 1 — the answer is 4 cells: (0, 2), (1, 0), (1, 1) and (2, 0).

417 Pacific Atlantic Water FlowWalkthrough · 1×

Example: find the cells of a 3 × 3 island whose rain can run down to both oceans, by climbing up from each ocean’s coast.

012012123452311pacifictop and left012012123452311atlanticbottom and rightcall stacktop on the right—in both—
not reached by this ocean’s climbon the call stackcurrent cellneighbour at least as high: climb to itlower neighbour: its water cannot run up herereached: its water flows to this ocean

pacific = empty set: the cells whose water reaches the Pacific. We fill it by climbing up from the coast, not by running down from every cell

01/67
restart · back · play · step
Speed
1function pacificAtlantic(heights):
2 pacific = empty set
3 atlantic = empty set
4 for each cell (row, col) on the top or left edge, not in pacific:
5 climb(row, col, pacific)
6 for each cell (row, col) on the bottom or right edge, not in atlantic:
7 climb(row, col, atlantic)
8 return cells in both pacific and atlantic
9
10function climb(r, c, ocean):
11 ocean.add((r, c))
12 for each neighbour (nr, nc) not in ocean:
13 if heights[nr][nc] >= heights[r][c]:
14 climb(nr, nc, ocean)
state
row
–
col
–
ocean
–
r
–
c
–
nr
–
nc
–
click a step to go back

← → step · space play/pause

Why it works

  1. Water runs from a cell down into a neighbour no higher than it. Reversed, a climb from the coast to neighbours at least as high reaches exactly the cells whose water can run down to that coast.
  2. So two climbs, one from each ocean’s coast, mark everything at once, instead of a separate downhill walk from every cell.
  3. A cell belongs to the answer exactly when both climbs reached it.

Complexity

Time O(rows × cols): each climb enters every cell at most once, and there are two climbs. Memory O(rows × cols) for the two sets and the call stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.