DSA problem
Pacific Atlantic Water Flow
There is an m x n rectangular island that borders both the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). The island is partitioned into a grid of cells where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). Water can flow from a cell to an adjacent cell only if the adjacent cell's height is LESS THAN OR EQUAL to the current cell's height. Return a 2D list of coordinates where rain water can flow from the cell to BOTH oceans.
The brute-force approach starts a DFS from each cell, traversing only toward smaller-or-equal heights, and checks whether both oceans are reachable. With up to m * n cells and a worst-case O(m * n) traversal each, this is O((m * n)^2) — too slow for the grid sizes typically tested.
The key insight is to INVERT the direction of flow. Water reaches a border ocean iff that ocean can also reach the cell by following the path in reverse, climbing UP (the reversed comparison becomes >=). So we run DFS from every border cell of each ocean, walking only to neighbors that are higher-or-equal, marking each visited cell in a per-ocean visited matrix. A cell is in the answer iff both visited matrices have it marked.
This reduces the work to two linear sweeps from the borders: each cell is visited at most a constant number of times for each ocean, giving O(m * n) time and O(m * n) space for the two visited matrices.
Examples
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]][[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]heights = [[1]][[0,0]]heights = [[2,1],[1,2]][[0,0],[0,1],[1,0],[1,1]]Constraints
- m == heights.length
- n == heights[r].length
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10^5
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.