Pacific Atlantic Water Flow
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Matrix
Problem
An island is an m × n grid, and heights[r][c] is the height of the cell in row r, column c. The Pacific touches the top and left edges of the island, the Atlantic the bottom and right edges.
Rain that falls on a cell flows to a neighbouring cell (up, down, left or right) whose height is less than or equal to its own, and from any cell on an edge it flows into the ocean that edge touches. Water can cross flat ground, but it never flows uphill.
Return the coordinates [r, c] of every cell from which rain can reach both oceans, in any order.
The largest tests are 200 × 200. A flood fill that recurses from cell to cell can go 40,000 calls deep there, far beyond Python’s recursion limit, so use a queue or an explicit stack.
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 the 5 in the middle, water runs up through the 3 and the 2 to the top edge (Pacific), and right through the 3 and the 1 to the right edge (Atlantic). The top-right and bottom-left corners touch both oceans directly.
Input: heights = [[1]] Output: [[0,0]]
A single cell is on all four edges, so it touches both oceans.
Constraints
- m == len(heights), n == len(heights[r])
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10^5
Approaches
- Follow the water from every cell — time O((m · n)²), space O(m · n)
Related problems
Start free on Cariara · Coding problems · System design studio
