Implement pacific_atlantic(heights) -> list[list[int]].
heights is a rectangular grid of non-negative integers describing an island's elevation. The Pacific touches the top and left edges of the grid, the Atlantic touches the bottom and right edges. Rain on a cell can move to a side-sharing neighbour whose height is less than or equal to the current cell's, and it drains into an ocean from any cell on an edge touching that ocean.
Return the coordinates [r, c] of every cell from which water can reach both oceans. Any order is accepted.
pacific_atlantic([
[1, 2, 3],
[8, 9, 4],
[7, 6, 5],
])
# [[0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
Here [0, 0] and [0, 1] only reach the Pacific, since everything to their right or below is higher.
Grids go up to 150×150, and searching downhill from every cell separately is too slow: aim for O(rows·cols). Avoid deep recursion (Python's default limit is about 1,000 frames).
Show hint
Instead of asking where each cell's water can go, ask which cells can send water to a given ocean, starting from that ocean's edge.