344. Pacific Atlantic Water Flow
An island is described by an m x n grid heights, where heights[r][c] is the elevation of the cell in row r, column c. The Pacific ocean touches the island's top and left edges; the Atlantic touches the bottom and right edges.
Rain lands on every cell. Water on a cell can move to any of its four neighbors (up, down, left, right) whose height is less than or equal to the current cell's height, and it spills into an ocean whenever it flows off an edge that ocean touches.
Return the coordinates [r, c] of every cell whose rainwater can reach both oceans. You may return the cells in any order — the grader normalizes them into row-major order before comparing.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation: Take cell (2, 2) with height 5: stepping left through 4 then 2 reaches the top rows and the Pacific, while stepping right through 3 then 1 falls off the right edge into the Atlantic. Seven cells manage both.
Example 2:
Input: heights = [[1, 2], [4, 3]]
Output: [[0,1],[1,0],[1,1]]
Explanation: Cell (0, 0) with height 1 sits on the Pacific but both neighbors are higher, so its water is trapped away from the Atlantic. The other three cells reach both oceans.
Constraints:
- 1 ≤ m, n ≤ 200
- 0 ≤ heights[r][c] ≤ 10⁵
Hints:
Simulating water from every cell separately works but repeats an enormous amount of exploration — each start re-walks the same slopes.
Flip the direction: instead of asking "can this cell drain to the ocean?", start AT the ocean borders and walk uphill (to neighbors with height >= current). Every cell you can climb to is a cell whose water can flow down to that ocean.
Run the uphill flood twice — once seeded from all Pacific border cells, once from all Atlantic border cells — and output the cells present in both visited sets.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Expected output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]