codejump
MediumPythonJavaScriptTypeScript

Graph — Pacific Atlantic Water Flow

Data StructuresGraphsDFSMatrix

solve(heights) — heights[r][c] is the height of a cell. The Pacific ocean
touches the top row and the left column; the Atlantic touches the bottom row
and the right column. Water flows from a cell to a 4-directional neighbour of
equal or lower height.

Return every cell [r, c] from which water can reach both oceans, sorted by
row and then by column.

Searching from every cell is too slow. Flip the problem: start from each ocean's
border cells and walk uphill (to neighbours that are equal or higher). A cell
reached by both searches is an answer.

Examples

solve([[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]])
  → [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
solve([[1]])          → [[0,0]]
solve([[1,1],[1,1]])  → [[0,0],[0,1],[1,0],[1,1]]

Sample tests

Test #1Classic 5×5 example
Input: [[[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]]
Test #2Single cell touches both oceans
Input: [[[1]]]
Output: [[0,0]]
Test #3Flat terrain
Input: [[[1,1],[1,1]]]
Output: [[0,0],[0,1],[1,0],[1,1]]