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]]