Pacific Atlantic Water Flow LeetCode 417

LeetCode 417 Pacific Atlantic Water Flow gives you an m x n integer matrix heights representing an island. The Pacific ocean touches the top and left borders of the island; the Atlantic ocean touches the bottom and right borders. Rain water can flow from a cell to any of its four neighbors if the neighbor's height is less than or equal to the current cell's height.

Your task is to return a list of all grid coordinates where rain water can flow to both the Pacific ocean and the Atlantic ocean. A cell can reach an ocean if there exists a path of non-increasing heights from that cell to any border touching that ocean.

This is a grid reachability problem with a directional constraint. Naively, you could try flooding from each cell toward both oceans, but that leads to O(m*n * m*n) worst-case time. The key insight is to invert the direction of flow.

The forward approach asks: from each cell, can water reach the Pacific? Can it reach the Atlantic? For each cell you run a DFS/BFS following non-increasing paths until hitting a border or dead end. With m*n cells each potentially traversing the entire grid, this is O((m*n)^2) in the worst case — too slow for 200x200 grids.

The reverse approach flips the direction of flow. Instead of asking "can water flow down from cell X to the ocean?", ask "what cells can the ocean reach by flowing uphill?" Start BFS/DFS from all Pacific border cells simultaneously, moving to neighbors with height greater than or equal to the current cell. Every cell visited is reachable from the Pacific. Do the same for Atlantic borders. The intersection of the two visited sets is the answer.

This transforms two separate O((m*n)^2) searches into two O(m*n) multi-source BFS/DFS passes — a dramatic improvement that fits easily within the 200x200 constraint.

Initialize a visited set pacific_reachable. Add all cells on the top row (row 0, all columns) and left column (all rows, col 0) as starting points — these border cells can trivially drain to the Pacific. Push all of them into the BFS queue (or use them as DFS starting nodes) simultaneously.

From each border cell, expand to its four neighbors. A neighbor is reachable from the Pacific if it has not been visited yet and its height is greater than or equal to the current cell's height. This uphill condition is the reverse of normal water flow. Mark each newly reachable cell and continue expanding.

After the traversal completes, pacific_reachable contains every cell whose water can drain to the Pacific ocean. The key property: if cell A can flow up to cell B (height[B] >= height[A]) in reverse BFS, then in the forward direction cell B's water can flow down to cell A and eventually reach the Pacific.

Repeat the same process for the Atlantic ocean. Initialize atlantic_reachable and seed it with all cells on the bottom row (row m-1) and right column (col n-1). These cells border the Atlantic and can trivially drain to it. Run the same uphill BFS/DFS from these starting points.

After this second traversal, atlantic_reachable contains every cell whose water can drain to the Atlantic. The final answer is all cells that appear in both pacific_reachable and atlantic_reachable — the intersection of the two sets.

Collect the result by iterating over all cells and checking membership in both sets. Since set lookup is O(1), the final collection step is O(m*n). Total time complexity is O(m*n) and space complexity is O(m*n) for the two visited sets.

Both BFS and DFS produce correct results for this problem. BFS uses a deque and processes cells level by level from the border inward. DFS uses either explicit recursion or a stack. The asymptotic complexity is identical: O(m*n) time and O(m*n) space for both approaches.

BFS tends to use more memory during execution because the queue can hold up to O(m*n) cells at once, while DFS only holds the current path on the call stack. However, recursive DFS risks hitting Python's recursion limit on large 200x200 grids — use iterative DFS or BFS if recursion depth is a concern.

In interviews, BFS is often preferred for grid problems because it naturally models the multi-source "flood from the border" pattern. DFS produces slightly shorter code in Python and is easier to write from memory. Choose based on your comfort level; the grader accepts either.

In Python: create two sets pacific and atlantic. Define a bfs(starts, reachable) helper that takes a list of border cell coordinates and fills the reachable set. Call bfs with Pacific border cells, then Atlantic border cells. Return [[r,c] for r in range(m) for c in range(n) if (r,c) in pacific and (r,c) in atlantic].

In Java: use two boolean[][] arrays pacific and atlantic instead of sets. Define a void bfs(int[][] heights, boolean[][] visited, Deque<int[]> queue) method. Seed the queues with border cells, run BFS, then iterate all cells to collect those with both arrays marked true.

Time complexity is O(m*n) — each cell is visited at most once per BFS pass and there are two passes. Space complexity is O(m*n) for the visited sets/arrays and the BFS queue. The final result collection is also O(m*n).

Trapping Rain Water II (LC 407) is the 3D extension of the classic trapping rain water problem. It uses a min-heap BFS from the border inward, tracking the water level at each cell. The same "start from the border and work inward" intuition from Pacific Atlantic applies, though the mechanics differ significantly.

Longest Increasing Path in a Matrix (LC 329) is a related grid DFS problem where you traverse in increasing order. Unlike Pacific Atlantic which uses multi-source BFS, LIP uses memoized DFS from each cell. Both share the insight that grid traversal problems often benefit from reversing the direction of movement.

The grid BFS/DFS family — Number of Islands (LC 200), Rotting Oranges (LC 994), Flood Fill (LC 733) — all share the same BFS/DFS template. Pacific Atlantic stands out as the multi-source, two-pass variant where the key insight is reversing the flow direction to avoid an O(n^4) brute force.