Runoff Cells Reaching Both Coasts
A terrain grid gives the elevation of each cell. Water flows from a cell to neighbors of equal or lower height. The northwest borders touch one ocean and the southeast borders touch another. Find cells from which water can reach BOTH oceans.
Problem
Given an m x n integer matrix heights, the Pacific ocean touches the left and top edges and the Atlantic touches the right and bottom edges. Water flows from a cell to an adjacent cell (up/down/left/right) only if the neighbor's height is <= the current cell's height. Return all coordinates [r, c] from which water can flow to BOTH oceans.
Input
An m x n integer matrix heights with values in [0, 10^5].
Output
A list of [row, col] coordinates that reach both oceans.
Constraints
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10^5
Examples
Example 1
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]]
These cells drain to both the Pacific and Atlantic.
Example 2
Input
heights = [[1]]
Output
[[0,0]]
A single cell touches both oceans.