Pacific Atlantic Water Flow LeetCode 417

LeetCode 417 — Pacific Atlantic Water Flow — gives you an m x n matrix of heights. The Pacific ocean touches the top and left edges. The Atlantic ocean touches the bottom and right edges. Water flows from a cell to a neighboring cell with equal or lower height. Find all cells from which water can reach both oceans.

The forward approach — DFS from every cell to check if it reaches both oceans — is O(m*n * m*n) in the worst case. Many cells share paths, leading to massive redundant computation.

The reverse approach is the key insight: instead of flowing water downhill from each cell, flow water UPHILL from each ocean border. Cells reachable from the Pacific border (going uphill) can drain to the Pacific. Same for Atlantic. The intersection gives cells that can reach both.

Start from every Pacific border cell (top row + left column). DFS/BFS to neighbors with height >= current cell (uphill or equal — reverse of the natural downhill flow). Mark all reachable cells in a pacific_reachable boolean matrix.

Repeat from every Atlantic border cell (bottom row + right column). Mark reachable cells in an atlantic_reachable matrix. The traversal logic is identical — only the starting cells differ.

The answer is all cells where both pacific_reachable[i][j] AND atlantic_reachable[i][j] are true. These cells sit on paths that connect to both oceans. Collect and return their coordinates.

Consider 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]]. Pacific border: row 0 and col 0. Atlantic border: row 4 and col 4. DFS uphill from Pacific covers cells that can drain to Pacific.

Pacific DFS from (0,0)=1: neighbors (0,1)=2 >= 1 → visit. (1,0)=3 >= 1 → visit. Continue uphill. Eventually marks a region including cells like (0,4)=5, (1,3)=4, etc. Atlantic DFS from (4,4)=4: uphill to (3,4)=5, (4,3)=2 no (2<4)... continues similarly.

Intersection cells where both are reachable: (0,4), (1,3), (1,4), (2,2), (3,0), (3,1), (4,0). These 7 cells can drain to both oceans. For example, (2,2)=5 is a peak — water flows left/up to Pacific and right/down to Atlantic.

Use two boolean matrices: pacific[m][n] and atlantic[m][n]. DFS function takes (row, col, prev_height, visited_matrix). If out of bounds, already visited, or height < prev_height: return. Mark visited. Recurse on four neighbors with current height as prev_height.

Initiate DFS: for each cell in row 0 and col 0, call dfs(r, c, heights[r][c], pacific). For each cell in row m-1 and col n-1, call dfs(r, c, heights[r][c], atlantic). The prev_height starts as the cell's own height.

After both DFS passes, iterate the grid. If pacific[i][j] and atlantic[i][j], add [i, j] to the result. Return the result list.

Python: pacific = set(). atlantic = set(). def dfs(r, c, prev, visited): if (r,c) in visited or out of bounds or heights[r][c] < prev: return. visited.add((r,c)). For dr, dc in dirs: dfs(r+dr, c+dc, heights[r][c], visited). Call for borders. Return [[r,c] for r,c in pacific & atlantic].

Using sets for visited is clean in Python. The intersection operator & gives the answer directly. For larger grids, boolean arrays are faster than sets due to O(1) lookup vs hash overhead.

Java: boolean[][] pacific = new boolean[m][n], atlantic = new boolean[m][n]. DFS with the same uphill condition. Collect result with nested loop checking both arrays. Use an int[][] dirs array for cleaner neighbor iteration.

Time complexity is O(m * n). Each DFS pass visits every cell at most once (marked as visited). Two passes: 2 * O(m * n) = O(m * n). The final intersection scan is O(m * n). Total: O(m * n).

Space complexity is O(m * n) for the two boolean matrices (or sets) and the DFS recursion stack. The recursion stack can reach O(m * n) depth in the worst case (spiral path). BFS avoids this with O(m * n) queue space instead.

This is optimal — every cell must be examined at least once to determine ocean reachability. The reverse approach achieves this with exactly two passes instead of m * n individual DFS runs.

Surrounded Regions (LeetCode 130) uses the same reverse thinking: DFS from border O cells to find un-surrounded regions. Both problems start from the boundary and propagate inward. The structural similarity is striking.

Longest Increasing Path in a Matrix (LeetCode 329) also uses DFS on a grid with height comparisons. It finds paths going strictly uphill rather than tracing ocean reachability. The DFS memoization technique transfers between the two.

Number of Islands (LeetCode 200) and Shortest Bridge (LeetCode 934) are simpler grid DFS/BFS problems. Together with Pacific Atlantic Water Flow and Surrounded Regions, they form the complete grid traversal curriculum.