LeetCode Pacific Atlantic Water Flow

LeetCode 417 — Pacific Atlantic Water Flow — is a problem 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.

Brute Force

For every cell, run a DFS that follows the “flows downhill or flat” rule and check whether it reaches a Pacific border cell and an Atlantic border cell. The traversal touches up to m * n cells per start, and there are m * n starts.

def pacificAtlantic(heights):
    m, n = len(heights), len(heights[0])
    def reaches(r, c, target):
        stack = [(r, c)]
        seen = {(r, c)}
        while stack:
            i, j = stack.pop()
            if target(i, j):
                return True
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni, nj = i + di, j + dj
                if (0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen
                        and heights[ni][nj] <= heights[i][j]):
                    seen.add((ni, nj))
                    stack.append((ni, nj))
        return False
    pac = lambda i, j: i == 0 or j == 0
    atl = lambda i, j: i == m - 1 or j == n - 1
    out = []
    for r in range(m):
        for c in range(n):
            if reaches(r, c, pac) and reaches(r, c, atl):
                out.append([r, c])
    return out

Total cost: O((m * n)^2). Brutal for any nontrivial grid.

Optimal Solution

Flip direction. Start BFS or DFS from every Pacific-border cell, but reverse the rule: move only when the neighbor’s height is greater than or equal to the current cell’s height. Mark every reachable cell as “Pacific-reachable.” Repeat from Atlantic-border cells for “Atlantic-reachable.” The answer is the intersection.

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]

Each cell is added to each set at most once, so the total work is linear in m * n.

Walk Through an 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. pac = {(0,0), (0,1), (1,0), (1,1)} once we also start from (0, 1) and (1, 0).
• 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.

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.

Related Problems

• LeetCode 200 — Number of Islands (canonical grid DFS)
• LeetCode 130 — Surrounded Regions (start from borders, then flip)
• LeetCode 1020 — Number of Enclaves (boundary BFS)
• LeetCode 994 — 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 alongside Surrounded Regions and Trapping Rain Water II. 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.