A rectangular plot of land is split into an m × n grid of square cells, and heights[r][c] is the height of the cell in row r, column c. Two oceans surround it: the Pacific runs along the top edge and the left edge, and the Atlantic runs along the bottom edge and the right edge.
Rain that lands on a cell can run into a neighbouring cell directly above, below, left or right of it, as long as that neighbour is no higher than the cell it leaves (equal height is fine). From any cell on an edge, water can run straight into the ocean along that edge.
Return the coordinates [r, c] of every cell from which rain can reach both oceans. You may list the cells in any order.
The cells [0,3] and [3,0] sit in corners, where both oceans meet. From the 6 at [1,1], rain runs up to the 2 above it and into the Pacific, or right through 5 and 3 into the Atlantic. The 4 at [2,2] is not listed: its only lower neighbours, the 1 to its right and the 2 below it, lead to the Atlantic alone.
The 3s form one flat rim that touches every edge, so rain on any of them can reach either ocean. The 1 lies on the bottom edge, so it reaches the Atlantic, but every neighbour is higher, so it can't reach the Pacific.
With a single row, every cell is on the top edge and the bottom edge at once.
Constraints
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 10⁵Asking, for each cell, where its water can go repeats a lot of work. Turn it around: start at each ocean and ask which cells can drain into it.
The direct question is about one cell: drop rain on it, let it run downhill (or across flat ground), and see which coasts it touches. Asking that for every cell is honest work, but it repeats itself. Cells next to each other usually drain along the same paths, and each cell's search walks those paths again from scratch.
Time O(m · n)Space O(m · n)
The full walkthrough and code are part of Premium