Pacific Atlantic Water Flow

Medium

You are given an m x n grid heights representing the height of each cell on an island. The Pacific Ocean touches the left and top edges, and the Atlantic Ocean touches the right and bottom edges.

Rain water flows from a cell to a neighbour (up, down, left, or right) only if the neighbour's height is less than or equal to the current cell's height. Water can flow into an ocean from any cell adjacent to that ocean.

Return a list of coordinates [r, c] from which water can reach both oceans. Return them sorted (by row, then column) so the result is unambiguous.

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]]

Example 2

Input:  heights = [[1]]
Output: [[0,0]]
Explanation: The single cell touches all four edges.

Constraints

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 10^5