The problem
Rain falls on a grid of heights. The Pacific touches the top and left edges, the Atlantic the bottom and right. Water flows to a neighbour with equal or lower height. List the cells from which water can reach both oceans.
Input: the 5 × 5 heights shown Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Picture it
Picture an island of hills between two oceans. Tracing every raindrop downhill is slow. Instead we start at each coast and walk uphill (to equal or higher cells), marking every cell the ocean can be reached from. Do this once for each ocean. Cells marked by both are the answer.
How to recognise it
- A grid of heights and a flow rule: water moves to a neighbour that is equal or lower.
- The question is about which cells can reach a target (here, two sets of border cells), not about a path itself.
- Several cells can be the goal, and you need the cells that satisfy two conditions at once (reach the Pacific and the Atlantic).
- With up to 200 × 200 = 40,000 cells, running a search from each cell is the thing to avoid.
Start with brute force
For every cell, walk downhill (to equal or lower neighbours) with a fresh visited set, and note whether the walk touches the Pacific border (top or left) and the Atlantic border (bottom or right). Keep the cell if both are true.
def pacific_atlantic_brute(h):
R, C = len(h), len(h[0])
res = []
for r in range(R):
for c in range(C):
seen, st = {(r, c)}, [(r, c)]
pac = atl = False
while st:
x, y = st.pop()
if x == 0 or y == 0: pac = True
if x == R - 1 or y == C - 1: atl = True
for nx, ny in nbrs(h, x, y):
if (nx, ny) not in seen and h[nx][ny] <= h[x][y]:
seen.add((nx, ny)); st.append((nx, ny))
if pac and atl:
res.append((r, c))
return res
Each of the R·C cells may search up to R·C cells, so time is O((R·C)²): for 200 × 200 that is about 1.6 × 10^9 steps in the worst case, too slow in Python. Space is O(R·C) for one visited set.
From brute force to the idea
- Find the waste. Thousands of cells flow into the same few border cells, and each brute-force search rediscovers the same downhill paths.
- Flip the question. Instead of asking "where does the water from this cell go?", ask "which cells can send water to this border?" That is one search that starts at the border and moves uphill.
- Reverse the rule. Water flows from a cell to a neighbour that is equal or lower. Going backwards, you step from a cell to a neighbour that is equal or higher, which is the test
h[nr][nc] >= h[r][c]inclimb. - Start from many cells at once.
climbbegins with the whole border (top and left for the Pacific, bottom and right for the Atlantic) in the queue and inseen. One breadth-first pass marks every cell that can reach that ocean. - Intersect. A cell that can reach both oceans is in both sets, so
pac & atlis the answer. The result is sorted.
The key idea: search backwards from the goals, once per ocean, instead of forwards from every cell.
The key idea
Reverse the flow: BFS/DFS uphill from each ocean’s border, then intersect. O(rows × cols).
Python solution
def pacific_atlantic(h):
R, C = len(h), len(h[0])
def climb(starts): # walk uphill
seen, q = set(starts), deque(starts)
while q:
r, c = q.popleft()
for nr, nc in nbrs(h, r, c):
if (nr, nc) in seen:
continue
if h[nr][nc] >= h[r][c]:
seen.add((nr, nc))
q.append((nr, nc))
return seen
top = [(0, c) for c in range(C)]
left = [(r, 0) for r in range(R)]
bot = [(R - 1, c) for c in range(C)]
right = [(r, C - 1) for r in range(R)]
pac = climb(top + left)
atl = climb(bot + right)
return sorted(pac & atl)
def nbrs(g, r, c): # in-grid neighbours
R, C = len(g), len(g[0])
for nr, nc in ((r+1, c), (r-1, c),
(r, c+1), (r, c-1)):
if 0 <= nr < R and 0 <= nc < C:
yield nr, ncLeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O((R·C)²): one search per cell | O(R·C): a visited set per search |
| Two reverse searches (shown code) | O(R·C): each ocean's search visits each cell at most once; the final sort adds O(k log k) for k result cells | O(R·C): two sets and a queue |
Edge cases
- One cell (
[[1]]): returns[(0, 0)], since it touches both oceans. - A single row or column: every cell touches a border of each ocean, so all cells are returned.
- Flat grid (all heights equal): every cell is returned, because equal heights count as flowing. This is why the comparison is
>=. - The result holds tuples, not lists, such as
(0, 4). Convert them if the caller needs[0, 4]. - Imports:
dequeis required.
Common mistakes
- Searching downhill from the border, which finds the wrong cells.
- Using
>instead of>=, which breaks on flat areas. - Seeding only one corner cell per ocean instead of the whole border.
- Returning the union of the two sets instead of the intersection.
- Running a full search from every cell and timing out.
Return how many cells can send water to the Pacific (top or left border) only. Describe what changes, then write it if you like.
Compare with our answer
You need only the first of the two searches, and you return its size instead of an intersection.
def reach_pacific(h):
R, C = len(h), len(h[0])
starts = [(0, c) for c in range(C)] + [(r, 0) for r in range(R)]
seen, q = set(starts), deque(starts)
while q:
r, c = q.popleft()
for nr, nc in nbrs(h, r, c):
if (nr, nc) not in seen and h[nr][nc] >= h[r][c]:
seen.add((nr, nc))
q.append((nr, nc))
return len(seen)
Time O(R·C), space O(R·C).
A strong answer mentions: searching uphill from the border, starting with every border cell in the queue, and that the corner cell appears twice in starts but only once in the set.
1. On a 200 × 200 height grid, you must list every cell that can drain to the left edge, with water moving to equal or lower neighbours. Which approach avoids repeated work?
One reverse search from the goal visits each cell once. A search from each cell repeats the same paths many times, and sorting by height cannot handle flat areas or cells with several neighbours.
2. Why does climb accept a neighbour when h[nr][nc] >= h[r][c]?
Water goes from a cell to an equal or lower neighbour, so a neighbour that is equal or higher can send water to the current cell. Equal heights are included, not skipped.
3. A learner changes >= to > in climb. Which input now returns a wrong answer?
In the first three inputs every cell is on a border, so every cell is already a starting cell. In the flat 3 × 3 grid, cells can only be reached through equal neighbours, which > refuses, so only the two corners (0, 2) and (2, 0) remain instead of nine cells.
Score 60% or more and the lesson is marked complete.