Pacific Atlantic Water Flow

Problem

You are given an m x n matrix of non-negative integers representing terrain heights on an island. The ocean touches the island on all four sides: the left and top edges border ocean A, the right and bottom edges border ocean B. Rain landing on a cell can flow to any of its four orthogonal neighbors whose height is less than or equal to its own, and from an edge cell it flows into the adjacent ocean. Return the coordinates of every cell from which water can reach both oceans, in any order.

• The matrix has at least one cell and at most 250 rows and 250 columns.
• Heights are non-negative integers no larger than one million.

Examples

• heights = [[1,2,3],[8,9,4],[7,6,5]] → [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]. The peak (1,1)=9 drains everywhere. (0,0)=1 and (0,1)=2 touch ocean A directly but every route toward ocean B goes uphill, so they are excluded; (0,2)=3 sits on both the top edge and the right edge and qualifies trivially.
• heights = [[9,8,7],[6,5,4],[3,2,1]] → [[0,0],[0,1],[0,2],[1,0],[2,0]]. Heights fall toward the bottom-right, so every cell drains to ocean B, but only cells actually on the top or left edge can reach ocean A.
• heights = [[2,2,2],[2,9,2],[2,2,2]] → all nine cells. Water can move between equal heights, so the ring reaches every edge, and the centre drains onto the ring.

Hints

1. Simulating a downhill flood from every cell repeats an enormous amount of work. Which cells trivially reach ocean A? Which trivially reach ocean B?
2. Instead of asking "where can water from this cell go?", ask "which cells can water reach this edge from?" What does the flow rule look like when you walk it backwards?
3. Start a traversal from every A-edge cell going uphill (to neighbors with height >= current), mark everything reached; do the same from the B edges; intersect the two marked sets.