417. Pacific Atlantic Water Flow

The trick that unlocks this problem is running the water backwards. Instead of asking “can this cell drain to both oceans?” you ask “which cells can each ocean reach if water flowed uphill?” — and that single inversion turns an $O((mn)^2)$ mess into a clean linear scan. It’s a staple of the graph traversal patterns family, where a multi-source flood fill does the heavy lifting.

The problem

You get a grid of cell heights. Water flows from a cell to a neighbor (up, down, left, right) only when the neighbor is at the same height or lower. The top and left edges border the Pacific; the bottom and right edges border the Atlantic. Return every cell from which water can reach both oceans. (Full statement on LeetCode.)

For a grid like

1 2 3
8 5 4
7 6 9

the perimeter cells sit against one ocean or the other, while a genuinely interior cell like the 5 in the center still drains both ways — it slides downhill to a Pacific edge going one direction and an Atlantic edge going the other.

Intuition: run the water uphill from each shore

The naive read is to launch a search from every cell and see if it can trickle down to both oceans. That’s a DFS per cell, so $O((mn)^2)$ in the worst case — too slow when the grid can be $200 \times 200$.

Flip the direction. A cell drains into an ocean exactly when there’s a downhill path from it to that ocean’s border. Reverse every arrow: start at the border and walk to neighbors that are higher or equal. Every cell you can reach that way is a cell that could have drained back to that border. So one flood fill from all Pacific-edge cells marks everything that reaches the Pacific, and a second from all Atlantic-edge cells marks everything that reaches the Atlantic.

The answer is just the intersection: cells marked by both floods. Because each cell is visited at most twice (once per ocean), the whole thing is linear:

$O(m \cdot n) \text{ time}, \quad O(m \cdot n) \text{ space}$

The >= comparison is the subtle part. We’re reversing downhill flow, so going backward means climbing to equal-or-greater heights — flat plateaus stay connected, which matches the problem’s “less than or equal” rule for the forward direction.

Solution

Two boolean grids track reachability. Seed a flood from every border cell of each ocean, then collect cells flagged in both. The flood uses an explicit stack rather than recursion — on a flat $200 \times 200$ grid a single reverse-flood can reach $mn \approx 40{,}000$ cells, deep enough to overflow Java’s default call stack, so the iterative version is the safe default here.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

class Solution {
    private static final int[][] DIRS = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int m = heights.length, n = heights[0].length;
        boolean[][] pacific = new boolean[m][n];
        boolean[][] atlantic = new boolean[m][n];

        // Left/right columns seed Pacific (col 0) and Atlantic (col n-1).
        for (int r = 0; r < m; r++) {
            flood(heights, pacific, r, 0);
            flood(heights, atlantic, r, n - 1);
        }
        // Top/bottom rows seed Pacific (row 0) and Atlantic (row m-1).
        for (int c = 0; c < n; c++) {
            flood(heights, pacific, 0, c);
            flood(heights, atlantic, m - 1, c);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (pacific[r][c] && atlantic[r][c]) {
                    result.add(List.of(r, c));
                }
            }
        }
        return result;
    }

    // Walk uphill from a border cell with an explicit stack (no recursion depth risk).
    private void flood(int[][] heights, boolean[][] seen, int sr, int sc) {
        if (seen[sr][sc]) return;          // a corner cell can be seeded twice — skip repeats
        int m = heights.length, n = heights[0].length;
        Deque<int[]> stack = new ArrayDeque<>();
        seen[sr][sc] = true;
        stack.push(new int[] {sr, sc});
        while (!stack.isEmpty()) {
            int[] cell = stack.pop();
            int r = cell[0], c = cell[1];
            for (int[] d : DIRS) {
                int nr = r + d[0], nc = c + d[1];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (seen[nr][nc]) continue;
                // Reverse flow: only step to a neighbor at least as high as here.
                if (heights[nr][nc] < heights[r][c]) continue;
                seen[nr][nc] = true;
                stack.push(new int[] {nr, nc});
            }
        }
    }
}

A recursive DFS reads a touch cleaner but risks that $O(mn)$ stack depth; the explicit-stack version does identical work, just keeping the frontier on the heap. A BFS queue would be equally valid — the traversal order doesn’t matter for reachability.

Complexity

Approach	Time	Space
Reverse flood from both oceans	$O(m \cdot n)$	$O(m \cdot n)$

Each cell is marked seen at most once per ocean, and every push does $O(1)$ work, so both floods together are $O(mn)$. The space is the two boolean grids plus the explicit stack, which can hold up to $O(mn)$ cells in the worst case.

In an interview

Say the inversion out loud before you touch the keyboard: “checking every cell downhill is quadratic, so I’ll flip it — flood inward from each ocean’s border to equal-or-higher neighbors, then intersect.” Naming why the comparison flips to >= is what separates a memorized solution from an understood one; the interviewer is watching for exactly that reasoning.

The common trap is the boundary check colliding with the height check — guard the array bounds first, then compare heights, or you’ll index out of the grid on edge cells. The multi-source flood-fill idea here is the same one behind Number of Islands, and if you want the graph-modeling muscle it leans on, Clone Graph drills the traversal-with-state pattern. Both live under the graph traversal patterns hub.

References

• LeetCode 417 — Pacific Atlantic Water Flow