Pacific Atlantic Water Flow
Pacific Atlantic Water Flow is a medium Graphs problem from the Blind 75. The key pattern is reverse multi-source search, and a good solution runs in O(rows · cols) time.
Problem
Return sorted coordinates from which water can reach both the top/left ocean and bottom/right ocean by moving to equal or lower heights.
Examples
Example 1
Input
[[1,2],[4,3]]Output
[[0,1],[1,0],[1,1]]Example 2
Input
[[3,3,4],[2,5,3],[4,1,2]]Output
[[0,2],[1,1],[2,0]]Example 3
Input
[[2,1],[1,2]]Output
[[0,0],[0,1],[1,0],[1,1]]Approach
Search uphill from each ocean's border cells to find everything that can drain into it. Cells reached from both oceans are the answer.
| Pattern | Reverse multi-source search |
|---|---|
| Time | O(rows · cols) |
| Space | O(rows · cols) |
Watch out for
Water flows to equal heights too, so allow moves to neighbours that are greater or equal when searching in reverse.