The problem
An island is an m × n grid of heights. The Pacific Ocean touches its top and left edges; the Atlantic, its bottom and right edges. Rain flows from a cell to a neighbour (up, down, left, right) whose height is equal or lower, and from any edge cell into the ocean beside it.
Return every cell [r, c] from which rain can reach both oceans.
Examples
- Input
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] ]
- Output
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
- Input
heights = [[1]]
- Output
[[0, 0]]
Constraints
- 1 ≤ m, n ≤ 200
- 0 ≤ heights[r][c] ≤ 10⁵
The idea
Asking each cell “can I reach the ocean?” repeats the same walks. Turn it round: start at the ocean and walk uphill. Water can flow from a cell down to the Pacific exactly when the Pacific’s edge can “climb” to that cell through neighbours of equal or greater height.
So run one search from every Pacific edge cell, climbing, and mark what it reaches; do the same from the Atlantic edge. The answer is the cells marked by both.
- Time
- O(m · n) — each search visits a cell once
- Space
- O(m · n) — two sets of marks
Solution · every language run against every case
class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: rows, cols = len(heights), len(heights[0]) # Walk uphill from an ocean's edge: every cell reached can drain down into that ocean. def reach(starts): seen = set(starts) stack = list(starts) while stack: i, j = stack.pop() for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)): if 0 <= x < rows and 0 <= y < cols and (x, y) not in seen and heights[x][y] >= heights[i][j]: seen.add((x, y)) stack.append((x, y)) return seen pacific = reach([(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)]) atlantic = reach([(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)]) return [[r, c] for r in range(rows) for c in range(cols) if (r, c) in pacific and (r, c) in atlantic]