You are given an m x n integer matrix heights that represents the elevations on an island. The entry heights[r][c] gives the height of the cell at row r, column c. The Pacific Ocean lies along the top and left edges of the grid, while the Atlantic Ocean lies along the bottom and right edges.
Rainwater on any cell can flow to an adjacent cell (horizontally or vertically) provided that the neighbor's height does not exceed the current cell's height. A cell that sits on the top row or left column can drain straight into the Pacific, and a cell on the bottom row or right column can drain straight into the Atlantic.
Return the list of all coordinates [r, c] from which rainwater can eventually reach both oceans. The answer may be presented in any order.
Example 1:
Input: heights = [[1,2],[4,3]]
Output: [[0,1],[1,0],[1,1]]
Explanation: Cell (0,0) touches the Pacific, but both of its neighbours are higher, so its water never reaches the Atlantic. Cell (1,1) touches the Atlantic and can flow into (0,1), which touches the Pacific. Cells (0,1) and (1,0) each touch both oceans directly.
heights = [[1,[[0,1], [1, 0], [1, 1]]
| 0 | 1 | |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 4 | 3 |
We have a 2x2 grid of heights. The Pacific Ocean touches the top and left edges, the Atlantic Ocean touches the bottom and right edges.
Example 2:
Input: heights = [[7]]
Output: [[0,0]]
Explanation: A single cell lies on all four edges.
Example 3:
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: Every border cell can move along the ring of equal heights to reach both oceans. The centre cell is lower than all of its neighbours, so its water is trapped.
Constraints:
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5heights = [[1,[[0,1], [1, 0], [1, 1]]
| 0 | 1 | |
|---|---|---|
| 0 | 1 | 2 |
| 1 | 4 | 3 |
We have a 2x2 grid of heights. The Pacific Ocean touches the top and left edges, the Atlantic Ocean touches the bottom and right edges.