Pacific Atlantic Water Flow

PracticeNeetCode ↗LeetCode ↗

Given an m × n grid of heights, water flows from a cell to a neighbor whose height is less than or equal to its own, in four directions. The Pacific touches the top and left edges; the Atlantic touches the bottom and right edges. Return every coordinate from which water can reach both oceans.

Example

Key Pointers

• Flowing downhill from every single cell to check which ocean it reaches is expensive — reverse the problem instead: flow uphill from each ocean's border inward.
• Run a DFS from every Pacific-border cell (moving to a neighbor only if its height is ≥ the current cell's) to mark everything reachable "in reverse"; repeat for the Atlantic border.
• The answer is exactly the intersection of the two reachable sets.

Step-by-Step Analysis

1. Seed two visited sets, pacific and atlantic, from their respective border cells (top row + left column; bottom row + right column).
2. DFS from each Pacific border cell, only stepping to a neighbor whose height is ≥ the current cell's height — this simulates water flowing backward, uphill, from the ocean.
3. Repeat the same DFS from each Atlantic border cell into the atlantic set.
4. Return every coordinate present in both sets.

Complexity

Time: O(rows · cols) — Space: O(rows · cols)

Code

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    if not heights:
        return []

    rows, cols = len(heights), len(heights[0])
    pacific, atlantic = set(), set()

    def dfs(r: int, c: int, visited: set, prev_height: int) -> None:
        if (r < 0 or r >= rows or c < 0 or c >= cols or
                (r, c) in visited or heights[r][c] < prev_height):
            return
        visited.add((r, c))
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            dfs(r + dr, c + dc, visited, heights[r][c])

    for c in range(cols):
        dfs(0, c, pacific, heights[0][c])
        dfs(rows - 1, c, atlantic, heights[rows - 1][c])

    for r in range(rows):
        dfs(r, 0, pacific, heights[r][0])
        dfs(r, cols - 1, atlantic, heights[r][cols - 1])

    return [[r, c] for r in range(rows) for c in range(cols) if (r, c) in pacific and (r, c) in atlantic]

Code Explanation

How the solution above works, piece by piece.

1. Reverse the question: start at the ocean edges and move uphill. A cell reached this way can drain back down to that ocean.
2. dfs stops at the grid edge, at visited cells, or at cells lower than the one it came from (heights[r][c] < prev_height).
3. Run it from the top row and left column into pacific, and from the bottom row and right column into atlantic.
4. Return the cells in both sets.
5. Each cell is visited at most once per ocean: O(rows × cols).

Visual Walkthrough

Running it on an example grid heights = [[1, 2, 3], [8, 9, 4], [7, 6, 5]]:

Video Explanation

NeetCode — Pacific Atlantic Water Flow, LeetCode 417