Pacific Atlantic Water Flow

Table of Contents +

Pacific Atlantic Water Flow looks scary at first. You see a grid of heights and two oceans. The trick that makes it easy is one idea. Instead of asking where water flows down to, you flip it and ask where water can climb up from. That one flip turns a hard problem into a simple grid search.

🎯 The Problem

You get a grid of heights. You must find every cell from which water can reach both oceans.

The rules:

Water sits on each cell. Each number is a height.
The Pacific Ocean touches the top edge and the left edge.
The Atlantic Ocean touches the bottom edge and the right edge.
Water flows from a cell to a neighbor only if the neighbor is the same height or lower.
Water never flows uphill.
Return every cell from which water can reach both oceans.

Let us take a small grid. The numbers are heights.

Input grid (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

Output (cells that reach BOTH oceans):
[0,4] [1,3] [1,4] [2,2] [3,0] [3,1] [4,0]

Explanation: from each listed cell, water can flow down or flat
to the Pacific edge AND down or flat to the Atlantic edge.

A cell reaches the Pacific if water can step down or flat all the way to the top or left edge. A cell reaches the Atlantic if it can step down or flat to the bottom or right edge. We want the cells that can do both.

Here is the picture. Pacific hugs the top and left. Atlantic hugs the bottom and right. The corners are shared.

🐢 Approach 1: Search Down From Every Cell (Brute Force)

The idea in one line: stand on each cell and try to walk down to each ocean.

The idea:

From a cell, walk only to neighbors that are the same height or lower.
If you reach a Pacific edge, this cell reaches the Pacific.
Do the same walk toward the Atlantic.
If a cell reaches both, add it to the answer.

Why it is weak:

You start a fresh search from every single cell.
For a grid with n cells, each search can touch almost all n cells.
So the cost grows like n times n.
Many cells share the same paths down to the ocean. You re-walk them over and over.

Here is the search-from-every-cell code:

def pacific_atlantic(heights):
    rows, cols = len(heights), len(heights[0])
    def reaches(r, c, ocean):
        seen = set()
        def dfs(x, y):
            if (x, y) in seen: return False
            seen.add((x, y))
            if ocean == "p" and (x == 0 or y == 0): return True
            if ocean == "a" and (x == rows - 1 or y == cols - 1): return True
            return any(0 <= nx < rows and 0 <= ny < cols and heights[nx][ny] <= heights[x][y] and dfs(nx, ny) for nx, ny in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)))
        return dfs(r, c)
    return [[r, c] for r in range(rows) for c in range(cols) if reaches(r, c, "p") and reaches(r, c, "a")]

⚡ Approach 2: Reverse Flow With DFS (Best)

The idea in one line: start at the ocean and climb inland, marking every cell the ocean can reach.

The idea:

Forward flow asks “can this cell reach the ocean?”
Reverse flow asks “starting at the ocean, which cells can it reach by climbing up?”
Both questions give the same set of cells. The reverse one is far cheaper.

How it works:

Start from all the ocean edge cells together. This is a multi source search.
Multi source means you begin from many cells at once, not one.
The rule flips. Forward, water drops to a lower or equal neighbor. Reverse, you climb to a neighbor of the same height or higher.
DFS dives deep along one path using recursion.
Spread once from the Pacific edge and mark every cell it reaches.
Spread once from the Atlantic edge and mark every cell it reaches.
The answer is every cell marked by both.

Why it is fast:

One spread from the whole edge replaces many spreads from inside cells.
Each cell is visited a small fixed number of times. So the cost is O(n).

Here is the reverse-flow DFS code:

def pacific_atlantic(heights):
    rows, cols = len(heights), len(heights[0])
    def flow(starts):
        seen = set(starts); stack = list(starts)
        while stack:
            r, c = stack.pop()
            for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen and heights[nr][nc] >= heights[r][c]:
                    seen.add((nr, nc)); stack.append((nr, nc))
        return seen
    pac = flow([(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)])
    atl = flow([(rows-1, c) for c in range(cols)] + [(r, cols-1) for r in range(rows)])
    return [[r, c] for r, c in pac & atl]

🪣 Approach 3: Reverse Flow With BFS (Alternative)

The idea in one line: same reverse climb, but spread in layers with a queue.

The idea:

BFS spreads layer by layer instead of diving deep.
A queue is a line. You add to the back and take from the front.

How it works:

Load every Pacific edge cell into the queue and mark them.
Pop a cell and push its unvisited neighbors that are the same height or higher.
Repeat for the Atlantic edge in its own queue.
Keep the cells marked by both.

Why pick it:

It visits the exact same cells as DFS, so the answer matches.
It avoids deep recursion. So it is safer on a very large grid.

Here is the spread from the Pacific edge. It climbs inward to higher or equal cells.

Steps to Solve

Make two grids of marks the same size as the input. One for Pacific, one for Atlantic. All marks start as false.
Start a search from every Pacific edge cell. The Pacific edge is the top row and the left column.
In that search, move to a neighbor only if its height is greater than or equal to the current cell. Mark each visited cell as Pacific reachable.
Do the same search starting from every Atlantic edge cell. The Atlantic edge is the bottom row and the right column. Mark each visited cell as Atlantic reachable.
Walk through every cell. If a cell is marked by both, add its position to the answer.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses recursive DFS and two sets of visited cells.

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],
]
R, C = len(heights), len(heights[0])


def dfs(r, c, reach):
    reach.add((r, c))                       # mark this cell reachable
    for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < R and 0 <= nc < C:
            if (nr, nc) not in reach and heights[nr][nc] >= heights[r][c]:
                dfs(nr, nc, reach)          # climb to higher or equal


pacific, atlantic = set(), set()
for i in range(R):
    dfs(i, 0, pacific)        # left column
    dfs(i, C - 1, atlantic)   # right column
for j in range(C):
    dfs(0, j, pacific)        # top row
    dfs(R - 1, j, atlantic)   # bottom row

answer = []
for i in range(R):
    for j in range(C):
        if (i, j) in pacific and (i, j) in atlantic:
            answer.append("[%d,%d]" % (i, j))
print(" ".join(answer))

The output of the above code will be:

[0,4] [1,3] [1,4] [2,2] [3,0] [3,1] [4,0]

Now let us walk through the Python version line by line. The dfs function takes a cell and a set called reach. The first line reach.add((r, c)) marks the current cell as reachable from that ocean. We do this right away because we only ever call dfs on a cell that the ocean can reach.

Then we loop over the four neighbors with (dr, dc). The pairs (1, 0), (-1, 0), (0, 1), (0, -1) mean down, up, right, left. We compute nr, nc, the neighbor row and column.

The check 0 <= nr < R and 0 <= nc < C keeps us inside the grid. Without it we would read outside the array and crash. The next check (nr, nc) not in reach stops us from visiting the same cell twice. This is what keeps the search fast and stops endless loops.

The key line is heights[nr][nc] >= heights[r][c]. Remember we are doing reverse flow. We start at the ocean and climb inland. So we only step to a neighbor that is the same height or higher. That is the climb rule. If all checks pass we call dfs on the neighbor and the spread continues.

At the bottom we run dfs from every edge cell. The left column and top row feed the Pacific set. The right column and bottom row feed the Atlantic set. Finally we keep only the cells found in both sets. Those are the cells that reach both oceans.

⏱️ Time and Space Complexity

The brute force starts a fresh search from each of the n cells, and each search can touch n cells, so it costs O(n²). The reverse flow visits each cell a small fixed number of times across the two spreads, so it costs O(n), where n is the number of cells. Both need extra grids to mark visited cells, so space is O(n).

Approach	Time Complexity	Space Complexity
Search down from every cell (brute force)	O(n²)	O(n)
Reverse flow with DFS	O(n)	O(n)
Reverse flow with BFS	O(n)	O(n)

Tip

When a grid problem asks “which cells can reach an edge”, flip it. Start from the edge and spread inward. One spread from the whole edge replaces many spreads from inside cells.

🧩 Key Takeaways

✅ Flip the question. Instead of flowing down to the ocean, climb up from the ocean.
✅ Start from the whole ocean edge at once. This is a multi source search.
✅ The reverse climb rule is “move to a neighbor that is the same height or higher”.
✅ Run one spread per ocean, then keep the cells marked by both.
✅ This drops the time from O(n²) down to O(n).

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Max Area of Island
Surrounded Regions

Previous Course Schedule (Topological Sort) Next Max Area of Island

Pacific Atlantic Water Flow

Follow Us

Follow Us