Pacific Atlantic Water Flow
Part of Practice: Flood Fill & Regions
An island is a grid of cell heights (up to 200×200). The Pacific Ocean touches the top and left edges; the Atlantic touches the bottom and right edges. Rain water on a cell can flow to a 4-directional neighbor whose height is equal or lower, and it reaches an ocean by flowing off the matching edges. Return the coordinates of every cell from which water 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]]
From (2,2) with height 5, water can flow up 5→3→2→2 to the top edge (Pacific) and right 5→3→1 to the right edge (Atlantic). Each listed cell has some non-increasing path to both oceans.
- Input:
- heights = [[1]]
- Output:
- [[0,0]]
The single cell touches all four edges, so it drains into both oceans trivially.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.