Pacific Atlantic Water Flow

MediumGraphs · Reverse Multi-source DFS🧩 Graph DFS LeetCode #417 ↗Updated Oct 30, 2026

Problem

An m × n island has cell heights heights[r][c]. The Pacific touches the top and left edges, the Atlantic the bottom and right edges. Rain can move from a cell to a 4-directional neighbour whose height is ≤ its own, and edge cells drain into the adjacent ocean. List every cell [r, c] from which water can reach both oceans (any order).

Input12235 / 32344 / 24531 / 67145 / 51124Output[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Input[[1]]Output[[0,0]]

1 ≤ m, n ≤ 200 · 0 ≤ heights[r][c] ≤ 10⁵

Try it yourself

Java

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Don't pour water from every cell — run it backwards. Start from each ocean's shore and climb to neighbours that are ≥ the current height; that marks all cells able to drain into that ocean. The answer is the intersection of the two marked sets.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceSimulate Rain from Every Cell

Time O((m·n)²)Space O(m·n)

For each cell, DFS downhill (to neighbours with height ≤ current) using a fresh visited grid, noting whether the walk touches a Pacific edge (row 0 / col 0) and an Atlantic edge (last row / last col). Keep the cell if both were touched.

Java

static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    List<List<Integer>> res = new ArrayList<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++) {
            boolean[] ocean = new boolean[2]; // [0] Pacific, [1] Atlantic
            flow(heights, r, c, new boolean[m][n], ocean);
            if (ocean[0] && ocean[1]) res.add(List.of(r, c));
        }
    return res;
}
private void flow(int[][] h, int r, int c, boolean[][] seen, boolean[] ocean) {
    seen[r][c] = true;
    if (r == 0 || c == 0) ocean[0] = true;
    if (r == h.length - 1 || c == h[0].length - 1) ocean[1] = true;
    if (ocean[0] && ocean[1]) return; // both reached: stop early
    for (int[] d : DIRS) {
        int x = r + d[0], y = c + d[1];
        if (x >= 0 && y >= 0 && x < h.length && y < h[0].length
                && !seen[x][y] && h[x][y] <= h[r][c]) flow(h, x, y, seen, ocean);
    }
}

Faithful to the statement, but every cell may flood the whole grid again.

OptimalReverse DFS from Both Oceans

Time O(m·n)Space O(m·n)

Water flowing a → b needs h[b] ≤ h[a], so going backwards from the ocean we may step to a neighbour that is ≥. DFS from every Pacific shore cell into pac and every Atlantic shore cell into atl; each grid is filled once, so each cell is visited at most twice.

Java

static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int m, n;
int[][] h;
public List<List<Integer>> pacificAtlantic(int[][] heights) {
    h = heights; m = h.length; n = h[0].length;
    boolean[][] pac = new boolean[m][n], atl = new boolean[m][n];
    for (int r = 0; r < m; r++) { climb(r, 0, pac); climb(r, n - 1, atl); }
    for (int c = 0; c < n; c++) { climb(0, c, pac); climb(m - 1, c, atl); }
    List<List<Integer>> res = new ArrayList<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (pac[r][c] && atl[r][c]) res.add(List.of(r, c));
    return res;
}
private void climb(int r, int c, boolean[][] seen) { // walk the flow backwards (uphill)
    if (seen[r][c]) return;
    seen[r][c] = true;
    for (int[] d : DIRS) {
        int x = r + d[0], y = c + d[1];
        if (x >= 0 && y >= 0 && x < m && y < n && h[x][y] >= h[r][c]) climb(x, y, seen);
    }
}

Linear: two flood fills plus one intersection scan.

Pro tip

Multi-source BFS (queue seeded with all shore cells) gives the same O(m·n) result without deep recursion — mention it as the production-safe variant.

At a glance

Level	Approach	Time	Space
Brute Force	Simulate Rain from Every Cell	`O((m·n)²)`	`O(m·n)`
Optimal	Reverse DFS from Both Oceans	`O(m·n)`	`O(m·n)`

Common pitfalls

Using > instead of ≥ — equal-height plateaus must be crossed.
Mixing up the shores: Pacific = top + left, Atlantic = bottom + right.
Memoising per-cell answers in the brute force — plateaus form cycles, so memo is wrong.

Interview tips

Say “reverse the direction of flow” — it turns m·n searches into two.
Explain why the inequality flips to ≥ when walking backwards.
Name it: multi-source graph search from the boundary, like Surrounded Regions.

Pattern

Reverse multi-source flood fill → “which cells can reach target X”: search from X instead.

My notes saved in this browser