Find all cells in a height matrix from which water can flow to both the Pacific and Atlantic edges.
You are given an matrix of non-negative integers representing heights on a rectangular island.
Rainwater can flow from a cell to another cell that is directly adjacent up, down, left, or right, but only if the destination cell has height less than or equal to the current cell. Water on cells along the top and left edges can reach the Pacific Ocean, while water on cells along the bottom and right edges can reach the Atlantic Ocean.
Return all coordinates from which water can flow to both oceans.
A cell may be returned in any order.
Input Format
- A 2D integer matrix
heightswithmrows andncolumns. heights[r][c]is the height of cell(r, c).
Output Format
- Return a list of coordinates
[r, c]such that water from that cell can reach both the Pacific and Atlantic oceans. - The order of coordinates does not matter.
Constraints
- Heights are non-negative integers
- Movement is allowed only between orthogonally adjacent cells
- Water can move from a cell to a neighbor with height less than or equal to the current cell
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]]
Explanation
Run reachability from the Pacific borders (top and left) and from the Atlantic borders (bottom and right). The cells listed above are reachable from both searches.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.