Skip to main content
DSA patterns

Pacific Atlantic Water Flow

mediumGraphsGoogleAmazonUber

Problem statement

You are given a grid heights describing an island. The Pacific Ocean touches the island's top and left edges; the Atlantic Ocean touches its bottom and right edges.

Rain falling on a cell can flow to a neighbour directly up, down, left or right, but only if that neighbour is the same height or lower. Any cell on an edge can flow straight into the ocean that touches that edge.

Return every cell [r, c] from which water can reach both oceans. The answers here are listed row by row, left to right.

The same "can this reach both sides?" question comes up when checking that a node can reach two separate uplinks, or that a service can reach both a primary and a backup region under one-way routing rules.

Examples

Example 1

Input: 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: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Explanation: For example, water on [2,2] (height 5) can run up through 3 and 2 to the top edge (Pacific), and right through 3 and 1 to the right edge (Atlantic). Corners like [0,4] and [4,0] touch both oceans directly.

Example 1

Example 2

Input: heights = [[1]]

Output: [[0,0]]

Explanation: The single cell touches all four edges, so it drains into both oceans at once.

Hints

Hint 1: You could follow the water downhill from every cell and see which oceans it reaches. What does that cost when many cells share the same paths?

Approach

Optimal: Reverse BFS from both oceans

Intuition

Instead of asking "where does water from this cell go?" for every cell, ask "which cells can drain into the Pacific?" once. Start from the ocean and walk the water's path backwards: water flows from a cell to a lower-or-equal neighbour, so going backwards you may step from a cell to a neighbour that is the same height or higher.

Every cell on the top row and left column touches the Pacific, so put all of them in one queue — a multi-source BFS, like in 01 Matrix — and walk uphill. Every cell reached can drain into the Pacific. Do the same from the bottom row and right column for the Atlantic. The answer is the cells marked in both grids. Each search visits each cell once, so all the repeated work of the brute force disappears.

Steps

  1. Write climb(starts): mark every start cell, put them all in a queue, and BFS. From (r, c), move to an unmarked neighbour only if its height is >= heights[r][c]. Return the grid of marks.
  2. pacific = climb(top row + left column).
  3. atlantic = climb(bottom row + right column).
  4. Scan the grid row by row; add [r, c] wherever pacific[r][c] and atlantic[r][c] are both true.

Dry run

Example 1, looking at how [2,2] (height 5) is reached:

search path found (uphill) heights
Pacific (0,2) → (1,2) → (2,2) 2 → 3 → 5
Atlantic (2,4) → (2,3) → (2,2) 1 → 3 → 5

Both searches reach it, so [2,2] is in the answer. Here is how water from each of the seven answer cells drains (read left to right, downhill; "edge" means the cell already touches that ocean):

cell to the Pacific to the Atlantic
[0,4] edge (top row) edge (right column)
[1,3] → (0,3) → (1,4)
[1,4] → (1,3) → (0,3) edge (right column)
[2,2] → (1,2) → (0,2) → (2,3) → (2,4)
[3,0] edge (left column) → (4,0)
[3,1] → (3,0) → (4,1)
[4,0] edge (left column) edge (bottom row)

Other routes exist for some cells; one of each is enough. [2,1] (height 4) is reached by the Pacific search but not the Atlantic one — from height 4 the water can only go to its 2-high neighbours, and every way toward the bottom or right edge would mean climbing to 5 or 7 — so it is left out. Edge case: with a one-cell grid, the cell is a start in both searches.

Complexity

Time O(m·n) - Each of the two searches visits every cell at most once, because a cell is marked when it is first reached. Each visit checks four neighbours, which is constant work. A final scan over the grid collects the cells marked by both searches. Three passes over m·n cells is O(m·n) — about 40,000 cells for the largest grid instead of 1.6 billion steps.

Space O(m·n) - We keep two boolean grids, one per ocean, each m·n. Each search's queue can hold up to m·n cells. The output list is not counted.

from collections import deque
from typing import List


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        rows, cols = len(heights), len(heights[0])

        def climb(starts: List[tuple]) -> List[List[bool]]:
            reached = [[False] * cols for _ in range(rows)]
            queue = deque()
            for r, c in starts:
                if not reached[r][c]:
                    reached[r][c] = True
                    queue.append((r, c))
            while queue:
                r, c = queue.popleft()
                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 not reached[nr][nc]
                            and heights[nr][nc] >= heights[r][c]):
                        reached[nr][nc] = True
                        queue.append((nr, nc))
            return reached

        pacific = climb([(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)])
        atlantic = climb([(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)])
        return [[r, c] for r in range(rows) for c in range(cols) if pacific[r][c] and atlantic[r][c]]


if __name__ == "__main__":
    grid = [[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]]
    print(str(Solution().pacificAtlantic(grid)).replace(" ", ""))
    print(str(Solution().pacificAtlantic([[1]])).replace(" ", ""))
RecapThe whole problem in a few lines, for the night before
  • Spot it: find cells whose water can reach both oceans
  • Idea: search backwards: start from the Pacific edges and from the Atlantic edges, move to neighbours that are equal or higher, then return the cells reached from both
  • Cost: O(m x n) time, O(m x n) space
  • Trap: checking every cell forward is far slower; reverse the direction and climb uphill instead

Interview follow-ups

  • There are k oceans (or exits) instead of two. Which cells reach all of them?

    Run one reverse search per exit and keep a count per cell of how many searches reached it. Return the cells whose count is k. Time becomes O(k·m·n), and memory can stay O(m·n) by reusing one count grid and one visited grid per search.

  • Which cells reach *neither* ocean?

    Use the same two searches and return the cells marked by neither. No extra walking is needed — just a different condition in the final scan. Time and space stay O(m·n). In the infra version, these are the nodes with no path to any exit, which is exactly what you'd alert on.

  • Heights change over time (say, one cell at a time). How do you keep the answer fresh?

    Rerunning both searches costs O(m·n) per change. A change that lowers a cell can only remove reachability from cells above it, and raising a cell can only add some; you can limit the new search to the area around the changed cell. For a first answer in an interview, explain the full rerun and then this local update as an improvement.

Frequently asked questions

There are m·n cells but only two oceans. Searching from each cell repeats almost the same walk thousands of times. Searching from each ocean answers "can this cell drain here?" for every cell in one pass. The general rule: when many starting points ask about a few targets, start from the targets.

Water moves from a cell to a neighbour that is lower or the same height. Walking the path backwards from the ocean means taking those steps in reverse, so each step goes to a neighbour that is higher or the same height. The >= keeps flat areas connected, because water flows across equal heights too.

Yes — the order of visits doesn't matter, only which cells get marked. A recursive DFS is common in solutions for this problem. On a 200 × 200 grid it can go 40,000 calls deep, which overflows Python's default limit and can strain other languages, so an explicit stack or BFS is safer.

The problem accepts the cells in any order. Collecting them with a final row-by-row scan gives a stable, predictable order that matches the example. If your search collects them in a different order, sort the list before comparing with an expected answer.

It is reachability with one-way rules, asked from two directions at once. The same structure appears when checking which nodes can reach both of two exits: two upstream providers, a primary and a backup region, or two log sinks, when traffic may only move in one direction. The "search backwards from the targets" trick is what keeps it fast.