Pacific Atlantic Water Flow
MediumGraphs
An m x n island is given as a grid heights, where heights[r][c] is the height of the cell at row r, column c. The Pacific Ocean touches the island's top and left edges, and the Atlantic Ocean touches its bottom and right edges.
Rain falling on a cell can flow to a horizontally or vertically adjacent cell whose height is less than or equal to the current cell's height. Water flows from any cell on the island's border directly into the ocean(s) that border touches.
Return the coordinates [r, c] of every cell from which water can reach both oceans. The cells may be returned in any order.
Example 1
- Input:
- heights = [[1, 2, 2], [3, 2, 3], [2, 4, 5]]
- Output:
- [[0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
- Explanation
- Every cell except the top-left corner reaches both oceans. That corner has height 1 with a 2 to its right and a 3 below, and water cannot flow uphill, so it is stuck against the Pacific edge it already sits on.
Example 2
- Input:
- heights = [[3, 3, 3], [3, 1, 3], [3, 3, 3]]
- Output:
- [[0, 0], [0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1], [2, 2]]
- Explanation
- Water on any border cell can flow along the equal-height border to both oceans. The centre cell (height 1) is lower than all its neighbours, so its water cannot go anywhere and it is left out.
Example 3
- Input:
- heights = [[5, 1, 7]]
- Output:
- [[0, 0], [0, 1], [0, 2]]
- Explanation
- In a single row every cell touches the top edge (Pacific) and the bottom edge (Atlantic), so all three cells qualify.
Constraints
m == heights.length,n == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5