Pacific Atlantic Water Flow (LeetCode 417)

The problem

You get a grid of heights. The Pacific touches the top and left edges; the Atlantic touches the bottom and right edges. Rain on a cell flows to a neighbour (up, down, left, right) if that neighbour is the same height or lower, and from an edge cell straight into the ocean beside it. Return every cell from which water can reach both oceans.

Input:
1 2
4 3

Output: [[0,1], [1,0], [1,1]]

Cell (0,1) touches the top (Pacific) and the right (Atlantic). (1,0) touches the left and the bottom. (1,1) touches the bottom and right, and can also flow to (0,1) (height 2 ≤ 3) and on into the Pacific. Cell (0,0), height 1, is lower than everything around it, so its water can only go into the Pacific.

How to think about it

Start with brute force. From every cell, run a DFS downhill and see whether it reaches a Pacific edge and an Atlantic edge. That’s R·C searches, each up to O(R·C): O((R·C)²) in total, and the same paths are explored again and again.

The key insight: run the water backwards. Instead of asking “where can water from this cell go?”, ask ”which cells can send water to this ocean?”. Start at the ocean’s edge cells and walk uphill: from cell (r, c) you may step to a neighbour whose height is ≥ heights[r][c], because water could flow from that neighbour down to you. Everything you reach can drain into that ocean.

Two floods, one intersection. Flood once from the Pacific edges into a set pac, and once from the Atlantic edges into a set atl. Each flood visits each cell at most once. The cells in both sets are the answer. You’ve replaced R·C searches with exactly two.

Which pattern is this? Multi-source flood fill from the boundary, run in reverse. The tell is “which cells can reach the edge” or “can reach both X and Y”. Surrounded Regions uses the same move.

Approach

1. Create two empty sets, pac and atl.
2. dfs(r, c, seen) adds (r, c) to seen and recurses into each in-bounds, unseen neighbour that is at least as high.
3. Start a dfs into pac from every top-row and left-column cell, and into atl from every bottom-row and right-column cell.
4. Return the cells in pac & atl, sorted.

Solution

def pacific_atlantic(heights):
    if not heights: return []
    R, C = len(heights), len(heights[0]); pac = set(); atl = set()
    def dfs(r, c, seen):
        seen.add((r, c))
        for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
            nr, nc = r+dr, c+dc
            # walk uphill: water could flow from (nr, nc) down to (r, c)
            if 0 <= nr < R and 0 <= nc < C and (nr,nc) not in seen and heights[nr][nc] >= heights[r][c]:
                dfs(nr, nc, seen)
    for c in range(C): dfs(0, c, pac); dfs(R-1, c, atl)    # top -> Pacific, bottom -> Atlantic
    for r in range(R): dfs(r, 0, pac); dfs(r, C-1, atl)    # left -> Pacific, right -> Atlantic
    return sorted([list(x) for x in pac & atl])             # can reach both
# pacific_atlantic([[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]])
#   -> 7 cells

Dry run

On the 2×2 grid [[1, 2], [4, 3]]:

The intersection is [[0,1], [1,0], [1,1]]. On the 5×5 grid in the code comment, pac and atl each hold 16 cells and they share 7: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].

Complexity

• Time: O(R·C). Each flood adds each cell to its set at most once and checks four neighbours. Two floods, plus the intersection and sort of at most R·C cells (the sort adds a log factor if you count it).
• Space: O(R·C) for the two sets and the recursion stack.

Edge cases and pitfalls

• Empty grid returns []. A single cell touches all four edges, so it’s in the answer.
• Wrong comparison direction. The reverse walk goes to neighbours that are ≥ the current height. Using <= floods downhill, which answers a different question.
• Strict > misses flat areas: water flows between cells of equal height.
• One shared seen set for both oceans mixes them up. Each flood needs its own set.
• Recursion depth on large grids. Use BFS or an explicit stack if the grid can be hundreds of cells across.

Related problems

• Surrounded Regions (LeetCode 130): flood from the border to find what’s connected to the edge.
• Number of Islands (LeetCode 200): the plain flood fill this builds on.
• Swim in Rising Water (LeetCode 778): heights on a grid again, now minimising the highest point on a path.