Cells That Drain to Both Oceans
You are given a grid heights of whole numbers. Each cell is a piece of land, and its number is the height of that land.
The grid is an island between two oceans:
- the North-West ocean touches every cell of the top row and every cell of the left column;
- the South-East ocean touches every cell of the bottom row and every cell of the right column.
Rain falls on every cell. Water can move from a cell to a neighbour cell directly up, down, left or right, but only if the neighbour's height is less than or equal to the current cell's height. A cell that touches an ocean can pour its water straight into that ocean.
Return every cell [row, col] from which water can reach both oceans. Sort the list by row, and by col when rows are equal.
Hint: instead of checking each cell on its own, go the other way. Start from all cells next to one ocean and walk to neighbours that are as high or higher. Every cell you reach can drain into that ocean. Do this for both oceans and keep the cells reached both times.
Examples
Example 1
- Input:
- [[2,3,4],[1,6,5],[3,2,1]]
- Output:
- [[0,2],[1,1],[1,2],[2,0]]
Cell [0, 2] is in the top row and the right column, and cell [2, 0] is in the bottom row and the left column, so each of them touches both oceans. Cell [1, 2] (height 5) touches the South-East ocean, and it can flow up to [0, 2] (4 <= 5), which touches the North-West ocean. Cell [1, 1] (height 6) can flow left to [1, 0] (1), which touches the North-West ocean, and right to [1, 2] (5), which touches the South-East ocean. No other cell can reach both.
Example 2
- Input:
- [[5,5],[5,5]]
- Output:
- [[0,0],[0,1],[1,0],[1,1]]
All heights are equal, so water can move anywhere. Every cell reaches both oceans.
Example 3
- Input:
- [[7,1,4]]
- Output:
- [[0,0],[0,1],[0,2]]
With only one row, every cell is in both the top row and the bottom row, so every cell touches both oceans.
Constraints
1 <= heights.length <= 71 <= heights[i].length <= 7, and every row has the same length.0 <= heights[i][j] <= 20
Run checks your code against the 3 examples. Submit checks it against all 153 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.