Skip to content
Codeloom
DSA

Pacific Atlantic Water Flow — Flood Inward From the Borders

Why reverse traversal beats per-cell flood fill, and how the intersection of two reach sets gives the answer.

·7 min read · By Codeloom
Intermediate 9 min read

What you'll learn

  • ✓Why reverse traversal beats per-cell flood fill
  • ✓How to seed BFS or DFS from grid borders
  • ✓The set-intersection finish that combines the two oceans
  • ✓How this pattern transfers to other "reachable from boundary" problems

Prerequisites

This problem is about reversing your point of view. The intuitive direction is to start at each cell and trace where water flows. The clever direction is to start at the oceans and ask where water could have come from. That single inversion turns an O(m^2 * n^2) brute force into a linear sweep.

The Problem

You are given an m x n grid of integer heights. Water flows from a cell to a neighbor (up, down, left, right) if the neighbor’s height is less than or equal to the current cell’s height. The top and left edges touch the Pacific; the bottom and right edges touch the Atlantic. Return all coordinates from which water can reach both oceans.

Intuition

Instead of asking “does water from cell (r, c) reach the ocean,” ask “starting at the ocean, can water have climbed up to cell (r, c)?” This swaps the comparison from <= to >=. Run BFS or DFS from every Pacific-border cell, marking every reachable cell as “Pacific-reachable.” Repeat from Atlantic-border cells for “Atlantic-reachable.” The answer is the intersection of the two sets.

Explanation with Example

Take the 2x2 grid [[1, 2], [4, 3]].

  • Pacific borders: (0, 0), (0, 1), (1, 0). Atlantic borders: (0, 1), (1, 0), (1, 1).
  • From (0, 0), pac reaches (0, 0). Climbing to (0, 1) needs 2 >= 1 — yes. From (0, 1), climbing to (1, 1) needs 3 >= 2 — yes. Eventually pac covers all four cells.
  • Atlantic seeded from (1, 0), (1, 1), (0, 1) reaches everything similarly.
  • Intersection: all four cells.

In a more uneven grid, only the cells that show up in both sets survive.

grid (heights):       Pacific reach (top/left):
[1 2 2 3 5]           [P P P P P]
[3 2 3 4 4]           [P P P P P]
[2 4 5 3 1]           [P P P . .]
[6 7 1 4 5]           [P P . . .]
[5 1 1 2 4]           [P . . . .]

Atlantic reach (bottom/right):
[. . . . A]          intersection (P AND A):
[. . . A A]          [. . . . *]
[. . A A A]          [. . . * *]
[. A A A A]          [. . * . *]
[A A A A A]          [* * . . .]

multi-source DFS climbs only when neighbor >= current.
Seed from oceans inward; answer is intersection of two reach sets

Code

def pacificAtlantic(heights):
    if not heights or not heights[0]:
        return []
    m, n = len(heights), len(heights[0])
    pac, atl = set(), set()

    def dfs(r, c, seen):
        seen.add((r, c))
        for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            ni, nj = r + di, c + dj
            if (0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen
                    and heights[ni][nj] >= heights[r][c]):
                dfs(ni, nj, seen)

    for c in range(n):
        dfs(0, c, pac)
        dfs(m - 1, c, atl)
    for r in range(m):
        dfs(r, 0, pac)
        dfs(r, n - 1, atl)

    return [[r, c] for r, c in pac & atl]
public List<List<Integer>> pacificAtlantic(int[][] heights) {
    int m = heights.length, n = heights[0].length;
    boolean[][] pac = new boolean[m][n];
    boolean[][] atl = new boolean[m][n];
    for (int c = 0; c < n; c++) {
        dfs(heights, 0, c, pac, m, n);
        dfs(heights, m - 1, c, atl, m, n);
    }
    for (int r = 0; r < m; r++) {
        dfs(heights, r, 0, pac, m, n);
        dfs(heights, r, n - 1, atl, m, n);
    }
    List<List<Integer>> out = new ArrayList<>();
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (pac[r][c] && atl[r][c]) out.add(Arrays.asList(r, c));
    return out;
}

private void dfs(int[][] h, int r, int c, boolean[][] seen, int m, int n) {
    seen[r][c] = true;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dirs) {
        int ni = r + d[0], nj = c + d[1];
        if (ni >= 0 && ni < m && nj >= 0 && nj < n
                && !seen[ni][nj] && h[ni][nj] >= h[r][c])
            dfs(h, ni, nj, seen, m, n);
    }
}
void dfs(vector<vector<int>>& h, int r, int c, vector<vector<bool>>& seen, int m, int n) {
    seen[r][c] = true;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    for (auto& d : dirs) {
        int ni = r + d[0], nj = c + d[1];
        if (ni >= 0 && ni < m && nj >= 0 && nj < n
                && !seen[ni][nj] && h[ni][nj] >= h[r][c])
            dfs(h, ni, nj, seen, m, n);
    }
}

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    int m = heights.size(), n = heights[0].size();
    vector<vector<bool>> pac(m, vector<bool>(n, false));
    vector<vector<bool>> atl(m, vector<bool>(n, false));
    for (int c = 0; c < n; c++) { dfs(heights, 0, c, pac, m, n); dfs(heights, m - 1, c, atl, m, n); }
    for (int r = 0; r < m; r++) { dfs(heights, r, 0, pac, m, n); dfs(heights, r, n - 1, atl, m, n); }
    vector<vector<int>> out;
    for (int r = 0; r < m; r++)
        for (int c = 0; c < n; c++)
            if (pac[r][c] && atl[r][c]) out.push_back({r, c});
    return out;
}

Edge Cases

  • An empty grid — return an empty list. Handle the falsy check up front.
  • A single row or single column — that row or column borders both oceans; every cell is in the answer.
  • A flat grid where all heights are equal — every cell can reach both oceans because the “greater than or equal” rule is permissive.
  • Very tall central peaks — water cannot climb up from the ocean, so peaks may still be in the answer if any path of nondecreasing heights connects them to both borders.

Complexity Analysis

Time is O(m * n) — each cell is touched once per ocean. Space is O(m * n) for the two sets plus the recursion or queue. The brute force is O((m * n)^2) and stops being practical around 30 x 30 grids.

If you find yourself reasoning about the constants, the Big-O notation post is the right refresher.

How to Explain It in an Interview

Open with the inversion. “Instead of asking ‘does water from cell (r, c) reach the ocean,’ I ask ‘starting at the ocean, can water have climbed up to cell (r, c)?’” Explain that this swaps the comparison from <= to >=. Then describe the two-set strategy: one set per ocean, intersect at the end.

If the interviewer pushes on BFS vs DFS, say either works; DFS is fewer lines, BFS gives a more even memory profile for huge grids. If they ask about diagonal moves, the algorithm is unchanged — just add more directions to the offsets.

  • Number of Islands (canonical grid DFS)
  • Surrounded Regions (start from borders, then flip)
  • Number of Enclaves (boundary BFS)
  • Rotting Oranges (multi-source BFS)

Note the recurring pattern: when a problem cares about boundary-reachability, seed your traversal from the boundary.

Wrap up

Pacific Atlantic is the cleanest example of a problem that gets easier when you walk it backward. Add it to your mental catalog of “reverse the direction” tricks. Once you internalize multi-source traversals from the border, an entire category of grid problems becomes routine — including the ones that show up in BFS and DFS practice.

Related articles