Pacific Atlantic Water Flow: reversing the current to find reachability

The setup is elegant. An island sits between two oceans: Pacific on the top and left edges, Atlantic on the bottom and right edges. Rain falls, water flows downhill (or stays level), and you want every cell that can reach both oceans. Forward from each cell to both oceans — that's the obvious read. And it is also the slow one.

The key observation is that water flow is reversible in a useful way. Instead of asking "can water leave this cell and eventually hit the Pacific border?", ask "can water arriving from the Pacific border eventually reach this cell?" The condition just flips: instead of requiring the neighbor to be <= the current cell (downhill), you require it to be >= (uphill, in the reverse direction). You start DFS from every cell already touching the ocean and flood inward. Any cell reachable from Pacific boundary DFS and also reachable from Atlantic boundary DFS is a valid answer.

That is the whole idea. Everything below is making it precise and efficient.

The problem

There is an m x n island bordered by the Pacific Ocean on the top and left edges and the Atlantic Ocean on the bottom and right edges. Given an integer matrix heights where heights[r][c] is the height of cell (r, c), water can flow to a neighboring cell (north, south, east, west) only if that neighbor's height is less than or equal to the current cell's height. Return all cells from which rain water can reach both oceans. Full statement: LeetCode 417.

Constraints:
- m == heights.length
- n == heights[r].length
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10^5

What the constraints force

The grid is m x n with 1 <= m, n <= 200. That puts the cell count at up to 40 000, and the brute force at up to 40 000 * 40 000 = 1.6 * 10^9 operations — clearly too slow for a timed test. O(mn) is the target, and it is achievable.

Heights are in [0, 10^5]. No negatives, so no sign tricks. The values can be equal — water can flow between equal-height cells — which is why the condition is >= (not strict >). That boundary case (plateaus) bites people who write > instead of >=.

The grid is always at least 1x1. The single-cell case is m = n = 1, and that cell borders all four edges simultaneously — it trivially reaches both oceans. The code must not special-case this; it should fall out of the general logic.

Approach 1: Brute force — DFS from every cell

For each cell (r, c), run two independent DFS searches: one to check whether the cell can drain to the Pacific, one for the Atlantic. The DFS moves to a neighbor only when the neighbor's height is <= the current height (water flowing downhill). A cell "reaches" an ocean if the DFS steps onto a border cell adjacent to that ocean.

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        if not heights or not heights[0]:
            return []
 
        m, n = len(heights), len(heights[0])
        result = []
 
        def can_reach(r: int, c: int, ocean: str) -> bool:
            visited: set[tuple[int, int]] = set()
 
            def dfs(row: int, col: int) -> bool:
                if (row, col) in visited:
                    return False
                if ocean == "pacific":
                    if row == 0 or col == 0:
                        return True
                else:
                    if row == m - 1 or col == n - 1:
                        return True
                visited.add((row, col))
                for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                    nr, nc = row + dr, col + dc
                    if 0 <= nr < m and 0 <= nc < n and heights[nr][nc] <= heights[row][col]:
                        if dfs(nr, nc):
                            return True
                return False
 
            return dfs(r, c)
 
        for i in range(m):
            for j in range(n):
                if can_reach(i, j, "pacific") and can_reach(i, j, "atlantic"):
                    result.append([i, j])
 
        return result

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        if (heights == null || heights.Length == 0 || heights[0].Length == 0)
            return new List<IList<int>>();
 
        int m = heights.Length, n = heights[0].Length;
        var result = new List<IList<int>>();
 
        bool CanReach(int r, int c, string ocean) {
            var visited = new HashSet<(int, int)>();
 
            bool Dfs(int row, int col) {
                if (visited.Contains((row, col))) return false;
                if (ocean == "pacific") {
                    if (row == 0 || col == 0) return true;
                } else {
                    if (row == m - 1 || col == n - 1) return true;
                }
                visited.Add((row, col));
                int[,] dirs = { {0,1}, {1,0}, {0,-1}, {-1,0} };
                for (int d = 0; d < 4; d++) {
                    int nr = row + dirs[d, 0], nc = col + dirs[d, 1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n
                        && heights[nr][nc] <= heights[row][col]) {
                        if (Dfs(nr, nc)) return true;
                    }
                }
                return false;
            }
 
            return Dfs(r, c);
        }
 
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (CanReach(i, j, "pacific") && CanReach(i, j, "atlantic"))
                    result.Add(new List<int> { i, j });
 
        return result;
    }
}

Complexity. Time: O(m^2 * n^2). For each of the m*n cells you run two DFS searches, each potentially visiting all m*n cells. Space: O(mn) per DFS call for the visited set, plus O(mn) call stack in the worst case. This is too slow on 200x200 grids but passes for the conceptual test.

The brute force also hides a subtle redundancy: if (0, 3) is reachable from (1, 3) going to Pacific, and you later check (2, 3) going through (1, 3), you redo all the same work without caching. The reverse approach eliminates this entirely.

Approach 2: Reverse boundary DFS — the approach that ships

The reversal insight: instead of asking whether a cell can flow to the ocean, ask whether the ocean can flow to the cell — in reverse. Run two separate DFS passes: one starting from every Pacific border cell, one from every Atlantic border cell. During these reversed DFS passes, you move to a neighbor only if the neighbor's height is >= the current cell (because in the real direction, water would flow from the neighbor down to us — which is valid only if the neighbor is at least as high).

Mark every cell you can reach from Pacific borders in a boolean grid pac, and every cell reachable from Atlantic borders in atl. The answer is all cells where both are marked true.

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        if not heights or not heights[0]:
            return []
 
        m, n = len(heights), len(heights[0])
        pac = [[False] * n for _ in range(m)]
        atl = [[False] * n for _ in range(m)]
 
        def dfs(row: int, col: int, reachable: list[list[bool]], prev_height: int) -> None:
            if (row < 0 or row >= m or col < 0 or col >= n
                    or reachable[row][col]
                    or heights[row][col] < prev_height):
                return
            reachable[row][col] = True
            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                dfs(row + dr, col + dc, reachable, heights[row][col])
 
        # Seed from Pacific borders (top row + left column)
        for i in range(m):
            dfs(i, 0, pac, heights[i][0])
        for j in range(n):
            dfs(0, j, pac, heights[0][j])
 
        # Seed from Atlantic borders (bottom row + right column)
        for i in range(m):
            dfs(i, n - 1, atl, heights[i][n - 1])
        for j in range(n):
            dfs(m - 1, j, atl, heights[m - 1][j])
 
        return [[i, j] for i in range(m) for j in range(n)
                if pac[i][j] and atl[i][j]]

public class Solution {
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        if (heights == null || heights.Length == 0 || heights[0].Length == 0)
            return new List<IList<int>>();
 
        int m = heights.Length, n = heights[0].Length;
        bool[,] pac = new bool[m, n];
        bool[,] atl = new bool[m, n];
 
        void Dfs(int row, int col, bool[,] reachable, int prevHeight) {
            if (row < 0 || row >= m || col < 0 || col >= n
                || reachable[row, col]
                || heights[row][col] < prevHeight)
                return;
            reachable[row, col] = true;
            int[,] dirs = { {0,1}, {1,0}, {0,-1}, {-1,0} };
            for (int d = 0; d < 4; d++)
                Dfs(row + dirs[d,0], col + dirs[d,1], reachable, heights[row][col]);
        }
 
        // Seed from Pacific borders
        for (int i = 0; i < m; i++) Dfs(i, 0, pac, heights[i][0]);
        for (int j = 0; j < n; j++) Dfs(0, j, pac, heights[0][j]);
 
        // Seed from Atlantic borders
        for (int i = 0; i < m; i++) Dfs(i, n - 1, atl, heights[i][n - 1]);
        for (int j = 0; j < n; j++) Dfs(m - 1, j, atl, heights[m - 1][j]);
 
        var result = new List<IList<int>>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (pac[i, j] && atl[i, j])
                    result.Add(new List<int> { i, j });
        return result;
    }
}

Complexity. Time: O(mn). Each cell is visited at most once per ocean DFS pass, and there are two passes. Space: O(mn) for the two boolean grids plus O(mn) call stack in the worst case (a DFS that snakes through every cell).

Tracing the key example by hand

Take heights = [[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]] (the 5x5 grid from Example 1).

The Pacific borders seed: the entire left column (column 0) and the entire top row (row 0). Starting from those, the reversed DFS marks any cell reachable by traveling uphill.

After the Pacific DFS, pac looks like this (T = reachable, F = not):

T T T T T
T T T T T
T T T F F
T T F F F
T F F F F

The Atlantic borders seed: the entire right column (column 4) and the entire bottom row (row 4). After the Atlantic DFS, atl:

F F F T T
F F T T T
F T T T T
T T F T T
T T T T T

Intersecting the two grids cell by cell, the cells where both are T:

F F F T T   -> (0,4)
F F T T T   -> (1,3), (1,4)
F T T F F   -> (2,2)   (atl has (2,1)=T but pac has (2,1)=F)
T T F F F   -> (3,0), (3,1)
T F F F F   -> (4,0)

That is [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]], matching the expected output exactly.

Let me trace one cell manually to make this concrete: (2, 2) has height 5. The Pacific DFS reaches it because from the Pacific border at (0, 0) (height 1), you can travel to (1, 0) (height 3), to (2, 1) (height 4), to (2, 2) (height 5) — each step moving to a cell that is >= the previous (uphill in reverse, meaning downhill in the real direction). The Atlantic DFS reaches (2, 2) through (2, 4) (height 1) -> (2, 3) (height 3) -> (2, 2) (height 5). So cell (2, 2) earns its place.

Edge cases that deserve a line each

1x1 grid. The single cell borders all four edges simultaneously — both pac and atl are marked true after the very first DFS call, before the DFS even recurses. The loop seeds the same cell from both boundary sets. Result: [[0,0]]. No special case needed.

All cells the same height. Every cell can flow to every other cell since the condition is >= (equal heights are allowed). The DFS from Pacific borders floods the entire grid, and so does the DFS from Atlantic borders. Every cell ends up in the result. The code handles this because heights[neighbor] >= prev_height is satisfied everywhere.

Strictly increasing from top-left to bottom-right (a staircase). Only the cells in the top row and the rightmost column can reach both oceans — the top-right corner corner (0, n-1) trivially borders both. The Pacific DFS floods from top and left, the Atlantic DFS floods from bottom and right, and their intersection tends to be the diagonal region. No off-by-one because both border rows/columns are fully seeded.

Height 0 everywhere. Same as the all-same-height case. All cells drain everywhere; every cell is in the output.

m = 1 or n = 1 (single row or column). If m = 1, the only row borders both oceans (Pacific top, Atlantic bottom — same row). The entire row appears in the result. The boundary seeding covers the whole row for both DFS passes.

The >= vs > trap. If you write heights[nr][nc] < heights[row][col] (strict in the reverse direction), you block movement across equal-height plateaus. Cell (2,0) in the example has height 2, and (1,0) has height 3. The real forward flow goes from 3 downhill to 2, so in the reverse DFS from Pacific you go from (2,0) up to (1,0): the neighbor height 3 is >= 2. Strict > would block this. Always use >= in the reverse condition (equivalently, < in the "stop" guard, as written above).

Brute force versus reverse DFS — what you actually ship

I ship the reverse DFS without hesitation. The time difference is not marginal — it is O(m^2 n^2) versus O(mn), which on a 200x200 grid is roughly 1.6 billion operations versus 40 000. The space footprint is the same for both. The only cost is the inversion of intuition, which takes one sentence to explain in a code review: "we run DFS backward from each ocean boundary and intersect the reachable sets."

The brute force has its place as a mental stepping stone — it makes the correctness argument obvious — but it should never ship.

The pattern under the surface: multi-source reverse reachability

The underlying structure here is multi-source BFS/DFS with a reversed condition. A large class of grid problems asks "which cells can reach some set of boundary cells?" and the efficient answer is always: "flip the direction, seed from the boundary set, propagate inward." The key transfer:

• In the forward direction: move to neighbor if heights[neighbor] <= heights[current] (water flows down).
• In the reverse direction: move to neighbor if heights[neighbor] >= heights[current] (we climb up to find who could have flowed to us).

You see this same reversal in problems about surrounded regions, enclaves, and disconnected components. When you need to check membership in "cells that can reach the boundary," always think: seed from the boundary and ask "can the boundary reach this cell?"

The two-pass structure (one per target set) also generalizes. Here there are two oceans, so two passes. If there were three target sets, you would run three passes and intersect three boolean grids. The O(k * mn) cost for k target sets is linear in grid size for any fixed k.

Where this fits in the graphs series

This is the fifth problem in the graphs series, after Number of Islands (200), Clone Graph (133), Course Schedule (207), and Rotting Oranges (994). Those problems established the core traversal patterns: flood fill, BFS layered expansion, cycle detection via DFS coloring, and multi-source BFS for minimum distance. Pacific Atlantic adds a new pattern on top of that foundation — the reverse reachability from a boundary set — which is qualitatively different from all four predecessors.

Four siblings that work the same reversal or extend it:

Number of Enclaves (1020). Find cells from which you cannot walk off the grid boundary. Same reversal: DFS from every boundary cell, mark reachable cells, then count cells that were never marked. The "reverse from boundary" structure is identical; only the question (count vs. collect coordinates) changes.

Surrounded Regions (130). Mark all O cells on the boundary and flood inward; everything unmarked is surrounded and gets flipped to X. Another boundary-seed-then-invert pattern. The difference from Pacific Atlantic is that there is one boundary (the edge) instead of two disjoint ones.

Rotting Oranges (994). Multi-source BFS from all initially rotten cells simultaneously. No reversal needed because the source and target are both in the interior — but the "seed from multiple sources at once" logic is the same structural move. Compare this to seeding both Pacific border cells at once for the Pacific DFS.

Making a Large Island (827). Two-pass: first DFS to label each island component with an id, then sweep potential bridge cells. Not a strict reversal, but the "two DFS passes over the same grid to compute intersecting information" structure rhymes directly with Pacific Atlantic.