Pacific Atlantic Water Flow: Reverse DFS from Edges

You are given an m x n grid 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 any neighbor (up, down, left, right) that has an equal or lower height. Find all cells where water can flow to both oceans.

This is LeetCode 417: Pacific Atlantic Water Flow, and it is the problem that teaches you to think about DFS backwards. Instead of asking "where can water from this cell go?", you ask "which cells can reach this ocean?" It is a beautiful twist on the grid DFS pattern from Number of Islands.

Why the naive approach fails

The brute force idea is tempting: for every cell, run a DFS to see if it can reach both oceans. But with an m x n grid, that is O(m * n) cells, each potentially doing O(m * n) work in its DFS. Total: O((m * n)^2). Way too slow.

The problem with forward DFS is that you are doing redundant work. Cell (2, 3) might be explored dozens of times as part of different cells' DFS searches. We need a way to compute reachability for all cells at once.

The key insight: think backwards

Instead of asking "can this cell reach the Pacific?", flip the question: "which cells can the Pacific reach if water flowed uphill?"

Start from every Pacific border cell and DFS uphill (only move to neighbors with height >= current). Every cell you visit is reachable from the Pacific. Do the same thing starting from every Atlantic border cell. The answer is the intersection of those two sets.

Why does this work? If water at cell X can flow downhill to the Pacific border, then a reverse DFS from the Pacific border going uphill will reach cell X. It is the same path, just walked in reverse. And instead of running a separate DFS from every single cell, we run exactly two multi-source DFS passes: one from each ocean. Total work: O(m * n).

Visual walkthrough

Let's trace through the algorithm step by step. We will use a 5x5 grid and show how the two DFS passes work.

Two DFS passes. One from the Pacific border going uphill, one from the Atlantic border going uphill. Intersect the results. Done.

The solution

def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
    if not heights:
        return []

    rows, cols = len(heights), len(heights[0])
    pacific = set()
    atlantic = set()

    def dfs(r, c, reachable, prev_height):
        # Out of bounds, already visited, or can't flow uphill
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if (r, c) in reachable:
            return
        if heights[r][c] < prev_height:
            return

        reachable.add((r, c))

        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            dfs(r + dr, c + dc, reachable, heights[r][c])

    # DFS from Pacific border (top row + left column)
    for c in range(cols):
        dfs(0, c, pacific, heights[0][c])
    for r in range(rows):
        dfs(r, 0, pacific, heights[r][ 0])

    # DFS from Atlantic border (bottom row + right column)
    for c in range(cols):
        dfs(rows - 1, c, atlantic, heights[rows - 1][c])
    for r in range(rows):
        dfs(r, cols - 1, atlantic, heights[r][cols - 1])

    # Intersection: cells that can reach both oceans
    return [[r, c] for r, c in pacific & atlantic]

Let's break this down.

The DFS function takes a cell, a reachable set (either pacific or atlantic), and the height of the cell we came from. It only continues if the current cell's height is >= the previous height (going uphill). This is the reverse of water flowing downhill. We add the cell to reachable and explore all four neighbors.

The seeding step starts DFS from every border cell. The top row and left column border the Pacific. The bottom row and right column border the Atlantic. We pass heights[r][c] as the initial prev_height so the border cell itself always passes the height check.

The intersection at the end finds cells in both sets. The pacific & atlantic set operation does this in O(min(|pacific|, |atlantic|)) time.

Why we use sets instead of sinking

In Number of Islands, we modified the grid in place to mark visited cells. We cannot do that here because we need two separate visited sets (one per ocean). If we sank cells during the Pacific DFS, the Atlantic DFS would not be able to visit them.

Using two sets keeps the passes independent. Each cell can be in pacific, atlantic, both, or neither. The grid stays untouched throughout.

You could use two 2D boolean arrays instead of sets. That trades hash overhead for array indexing. Either way, the space is O(m * n).

Complexity analysis

Time is O(m * n). Each cell is visited at most once per DFS pass, and we do exactly two passes. The outer loops that seed the border cells also do O(m + n) work total.

Space is O(m * n) for the two sets and the recursion call stack. In the worst case (a grid that slopes from one corner), the DFS could go m * n levels deep.

Edge cases

Before submitting, check these:

• Single row or column: every cell borders both oceans (one directly, one through the row/column). All cells should be in the answer.
• Flat grid: all heights are equal. Water can flow anywhere. Every cell reaches both oceans. Return all cells.
• Descending from top-left: heights decrease going right and down. Only border cells are in the answer.
• 1x1 grid: the single cell touches both oceans. Return [[0, 0]].

The building blocks

This problem is built on three reusable pieces that CodeBricks drills independently:

1. Grid neighbor generation

The same direction-array pattern from every grid problem:

directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        # (nr, nc) is a valid neighbor

You saw this in Number of Islands, and you will see it in every grid problem going forward. The pattern never changes.

2. Multi-source DFS (seeding from edges)

Instead of DFS from a single starting cell, you seed from multiple starting cells:

# Seed from an entire border
for c in range(cols):
    dfs(0, c, reachable, heights[0][c])
for r in range(rows):
    dfs(r, 0, reachable, heights[r][0])

This is the same idea as multi-source BFS (used in Rotting Oranges) but with DFS. You iterate over all starting cells and launch DFS from each one. The reachable set prevents revisiting, so the total work across all launches is still O(m * n).

3. Reverse reachability (flip the direction)

The conceptual brick: instead of "can A reach B going forward?", you ask "can B reach A going backward?" In this problem, "backward" means going uphill instead of downhill. In other problems, it might mean reversing edge directions in a graph or starting BFS from the target instead of the source.

This is a general technique. Whenever you find yourself running DFS/BFS from many sources to check if they reach a common target, try flipping it: run one search from the target instead.

Common mistakes

1. Getting the height comparison backwards. In reverse DFS going uphill, you want heights[nr][nc] >= heights[r][c]. If you write <=, you are going downhill from the border, which finds cells that the border can flow to (the ocean), not cells that can flow to the border.

2. Forgetting to seed from both edges of each ocean. The Pacific has two borders (top row AND left column). The Atlantic has two borders (bottom row AND right column). If you only seed from one edge per ocean, you will miss cells.

3. Using one visited set for both passes. You need separate pacific and atlantic sets. If you reuse the same set, the Atlantic DFS will skip cells already visited by the Pacific DFS, even though those cells might also be reachable from the Atlantic.

4. Not handling the >= case. Water flows to neighbors with equal or lower height. That means your reverse DFS must accept equal or higher height. The >= comparison is correct, not strict >.

When to use this pattern

Look for these signals:

• The problem involves reaching a target from multiple sources (or vice versa)
• Brute-force DFS from every cell is too slow
• The problem mentions borders, boundaries, or edges of a grid
• You need to find cells that satisfy a reachability condition from two different directions

Problems that use the same reverse-DFS-from-edges pattern:

• Surrounded Regions (LeetCode 130): DFS from border 'O' cells, then flip everything not reached
• Walls and Gates (LeetCode 286): multi-source BFS from all gates to compute distances
• Shortest Bridge (LeetCode 934): find one island via DFS, then BFS to the other

From understanding to recall

You now see how reverse DFS from ocean borders turns an O((m * n)^2) brute force into a clean O(m * n) two-pass solution. The insight, thinking backwards, is the hard part. The code itself reuses grid neighbor generation and DFS flood fill, the same building blocks from Number of Islands.

But can you write the multi-source DFS seeding loop and the reverse height comparison from scratch under pressure? These details trip people up: which border belongs to which ocean, >= vs <=, separate sets vs shared set. They are not conceptually hard. They are recall challenges.

Spaced repetition closes that gap. You practice writing the Pacific/Atlantic seeding loops and the reverse DFS condition from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "reverse DFS from edges" in a problem, and the code flows out without hesitation.

Related posts

• Number of Islands - The foundational grid DFS problem, teaches the flood fill pattern that this problem builds on
• Course Schedule - Another graph problem where thinking about direction (forward vs backward edges) is the key insight
• Unique Paths - Grid problem with a different flavor: DP instead of DFS, but the same grid neighbor thinking

CodeBricks breaks Pacific Atlantic Water Flow into its grid-neighbor-generation, multi-source-DFS, and reverse-reachability building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a reverse DFS grid problem shows up in your interview, you do not think about it. You just write it.