A small island is drawn as a grid of square cells. The grid heights gives how high each cell is above the sea. heights[r][c] is the height of the cell in row r and column c.
The Arabian Sea touches the top side and the left side of the island. The Bay of Bengal touches the bottom side and the right side.
Monsoon rain falls on every cell. Water flows from a cell to a neighbour above, below, left or right, if that neighbour is not higher. Water can flow into a sea from any cell on a side that touches that sea.
Find every cell from which rain water can reach both seas. Return them as a list of [row, column] pairs.
Order of the answer: list the cells sorted by row, then by column. The judge compares your list with one fixed list.
Examples
Example 1:
Input: heights = [[2,6,3],[5,1,4],[9,2,8]]
Output: [[0,1],[0,2],[1,2],[2,0],[2,2]]
Explanation: Cell [2,0] has height 9. It touches the left and bottom sides, so it reaches both seas.
Cell [0,1] has height 6. It touches the top side, and it flows right to [0,2], which touches the right side.
Cell [0,0] has height 2. Both its neighbours are higher, so it can not reach the Bay of Bengal.
Example 2:
Input: heights = [[1,2,3,4]]
Output: [[0,0],[0,1],[0,2],[0,3]]
Explanation: There is only one row. It is both the top side and the bottom side, so every cell touches both seas.
Example 3:
Input: heights = [[4,3,2],[3,2,1],[2,1,0]]
Output: [[0,0],[0,1],[0,2],[1,0],[2,0]]
Explanation: Water runs downhill. The middle cell and the bottom-right corner reach only the Bay of Bengal.
Cell [1,0] is on the left side, and it flows down to [2,0] on the bottom side. So it reaches both seas.