A raindrop lands on a mountain map with two coastlines below it. Some peaks can drain to either coast; valleys may trap the drop on only one side.
You're given a rectangular matrix heights. Water may move from a cell to its top,
bottom, left, or right neighbor only when that neighbor's height is equal or lower.
The Pacific touches the top and left edges. The Atlantic touches the bottom and right
edges. Return every coordinate [row, col] whose water can reach both oceans.
A few ground rules:
[row, col].1 <= heights.length <= 2001 <= heights[r].length <= 2000 <= heights[r][c] <= 1_000_000Hints
A search from every cell keeps walking through the same slopes. Try starting from an ocean instead—but decide what movement rule must reverse too.
In a reverse search, move from a cell to neighbors of equal or greater height. Any cell reached this way has a downhill path back to that ocean.
Search once from all Pacific edges and once from all Atlantic edges. A coordinate belongs in the answer exactly when both searches reach it.
How would your approach change if water could also move diagonally to an equal-or-lower neighbor?
Visible cases
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
]
][
[
0,
4
],
[
1,
3
],
[
1,
4
],
[
2,
2
],
[
3,
0
],
[
3,
1
],
[
4,
0
]
]heights = [
[
1,
2
],
[
4,
3
]
][
[
0,
1
],
[
1,
0
],
[
1,
1
]
]heights = [
[
1,
2,
1
],
[
2,
9,
2
],
[
1,
2,
1
]
][
[
0,
1
],
[
0,
2
],
[
1,
0
],
[
1,
1
],
[
1,
2
],
[
2,
0
],
[
2,
1
]
]Interview signal
Start a breadth-first search from each cell. The search moves only to equal-or-lower neighbors and records whether it touches a Pacific edge and an Atlantic edge. Stop as soon as both flags are true.
from collections import deque
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
rows, cols = len(heights), len(heights[0])
def reaches_both(start_row: int, start_col: int) -> bool:
queue = deque([(start_row, start_col)])
seen = {(start_row, start_col)}
pacific = atlantic = False
while queue:
row, col = queue.popleft()
pacific = pacific or row == 0 or col == 0
atlantic = atlantic or row == rows - 1 or col == cols - 1
if pacific and atlantic:
return True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = row + dr, col + dc
if (0 <= nr < rows and 0 <= nc < cols and
(nr, nc) not in seen and
heights[nr][nc] <= heights[row][col]):
seen.add((nr, nc))
queue.append((nr, nc))
return False
return [
[row, col]
for row in range(rows)
for col in range(cols)
if reaches_both(row, col)
]One search can visit the whole matrix, and you may launch one from every cell. Time O((mn)²). Space O(mn) for a single BFS.
A multi-source reverse DFS is a depth-first search that begins from many destinations at once and follows every edge backward. Seed one search with the Pacific edges and one with the Atlantic edges. Because forward water moves downhill, each reverse search moves to an equal-or-higher neighbor.
Each search produces a set of cells that can drain to its ocean. Their intersection is the answer.
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
rows, cols = len(heights), len(heights[0])
def reverse_reachable(starts: list[tuple[int, int]]) -> set[tuple[int, int]]:
reached = set(starts)
stack = list(reached)
while stack:
row, col = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = row + dr, col + dc
if (0 <= nr < rows and 0 <= nc < cols and
(nr, nc) not in reached and
heights[nr][nc] >= heights[row][col]):
reached.add((nr, nc))
stack.append((nr, nc))
return reached
pacific_starts = (
[(0, col) for col in range(cols)] +
[(row, 0) for row in range(rows)]
)
atlantic_starts = (
[(rows - 1, col) for col in range(cols)] +
[(row, cols - 1) for row in range(rows)]
)
both = reverse_reachable(pacific_starts) & reverse_reachable(atlantic_starts)
return [[row, col] for row, col in both]Each ocean search reaches a cell at most once. Time O(mn). Space O(mn) for the two reachability sets and DFS stacks.
Ready to run.
3 cases are queued.
Visible testcase
Case 1
Expected
[
[
0,
4
],
[
1,
3
],
[
1,
4
],
[
2,
2
],
[
3,
0
],
[
3,
1
],
[
4,
0
]
]