656. Two-Ocean Flow
A rain gauge team has measured the height of every cell on a rectangular plateau, stored in heights. Water on a cell may flow to any of its four side neighbours whose height is less than or equal to its own. The north-west lake touches the top row and the left column of the plateau; the south-east lake touches the bottom row and the right column. A cell that sits on such an edge can pour into the lake directly.
Return the coordinates [row, column] of every cell from which water can reach both lakes, listed in increasing order of row and then column. If there is none, return an empty list. The target is O(R * C) time and O(R * C) extra space, so searching forward from each cell separately is too slow.
Example 1
- Input:
- heights = [[3,3,4],[2,5,3],[1,2,6]]
- Output:
- [[0,0],[0,1],[0,2],[1,0],[1,1],[2,0],[2,1],[2,2]]
- Explanation:
Water from the highest cells in the middle and right can flow towards both corners of the plateau, while the low west cells reach only the north-west lake.
Example 2
- Input:
- heights = [[1,2,3,4]]
- Output:
- [[0,0],[0,1],[0,2],[0,3]]
- Explanation:
With a single row every cell touches both the top and the bottom edge, so all four cells qualify.
Example 3
- Input:
- heights = [[9,8],[7,6]]
- Output:
- [[0,0],[0,1],[1,0]]
- Explanation:
All four cells sit on an edge of both lakes, so every cell qualifies.
Constraints
1 ≤ R, C ≤ 400
0 ≤ heights[i][j] ≤ 100000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(R * C)
- Space
- O(R * C)