← DSA Atlas
Dedicated problem page · #417

Pacific Atlantic Water Flow

MediumGraph DFS and BFSReverse flood-fill from bordersDFS from ocean edges
Solve on LeetCode ↗
417
MediumGraph DFS and BFSDFS from ocean edgesReverse flood-fill from borders

Pacific Atlantic Water Flow

Given an m x n grid of non-negative heights, water can flow from a cell to a neighboring cell (up/down/left/right) only if the neighbor's height is less than or equal to the current cell's height. The Pacific ocean touches the top and left edges; the Atlantic touches the bottom and right edges. Return the coordinates of every cell from which water can reach both oceans.

Open official problem prompt ↗
In plain English

Find every cell whose water can drain to both the Pacific and Atlantic oceans.

Picture it like this

Rather than release a raindrop on each mountain cell and watch where it ends up, imagine the sea level rising from each coast and flooding uphill; wherever both floods overlap, a raindrop could have run down to either shore.

Example
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]]
Why
Each listed cell has an ever-non-increasing downhill path reaching both the top/left border and the bottom/right border.
Constraints
m == heights.lengthn == heights[i].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
Pattern lesson

See the pattern, then code

Reverse flood-fill from borders
Recognition clue

Cells drain to an ocean along non-increasing paths and you must find cells reaching both — instead of searching downhill from each cell, flood uphill inward from the two ocean borders and intersect.

↗
Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Reverse the flow: starting at the Pacific border, move to neighbors whose height is greater than or equal to the current cell (water could have flowed the other way). Mark all cells reachable from each ocean, then the answer is the intersection.

New words, made simpleKnow these before the algorithm
Reverse flow
Traversing from ocean into land by stepping to cells of equal or greater height.
Multi-source start
Every border cell of an ocean seeds that ocean's search.
Set intersection
Cells present in both the Pacific-reachable and Atlantic-reachable sets.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
DFS downhill from each cell

Repeats work enormously; each cell re-explores overlapping downhill paths.

From every cell, search downhill to see if it reaches each ocean.

Time O((m*n)^2)Space O(m*n)
Best choiceReverse DFS from both borders

Each cell is visited at most twice; linear in the grid.

Flood uphill from Pacific and Atlantic borders separately, then intersect the reachable sets.

Time O(m*n)Space O(m*n)
The rule we keep true

Invariant

A cell is in the Pacific set exactly when there exists a non-increasing path from it to the top or left border; the reverse search adds a cell only when it can be reached by non-decreasing steps from that border, which is the same relation flipped.

Why this is correct

Reasoning

Water flows a->b when height[a] >= height[b]. Reversing the search means moving b->a when height[a] >= height[b], i.e. stepping to an equal-or-higher neighbor. So the set reachable backward from an ocean border is exactly the set of cells that can flow forward to it. Intersecting gives cells that reach both.

The algorithm in three movesSay these aloud before coding
1Create two visited sets, one per ocean

pac reachable from top row + left col

2DFS inward from every Pacific border cell, ascending or staying level

atl reachable from bottom row + right col

3DFS inward from every Atlantic border cell the same way

answer = pac & atl

4Intersect the two reachable sets

5Return the shared coordinates

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
Pac-edge0
Atl-edge1
both2
1 · Readtop row + left column
2 · AskWhich inland cells are >= their border neighbor?
3 · Update statepac grows inward
4 · ResultMarks reachable-to-Pacific cells
Key takeaway

Two floods grow inward from opposite borders; cells hit by both belong to the answer.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-4Empty guard

    Handle a grid with no rows or columns.

  2. 2
    Lines 8-11DFS bounds and height check

    Stop at the edge, at already-seen cells, or where the neighbor is lower than where we came from.

  3. 3
    Lines 12-18Mark and expand

    Record the cell, then continue uphill to all four neighbors passing the current height as the new floor.

  4. 4
    Lines 20-25Seed both oceans

    Launch searches from every border cell of the Pacific and the Atlantic.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A single cell grid, which reaches both oceans trivially
  • A single row or single column
  • All heights equal, so every cell reaches both oceans
  • Strictly increasing terrain where only certain corners qualify
!

Common beginner mistakes

  • Using strictly greater instead of greater-or-equal, which drops flat plateaus
  • Forgetting to pass the correct previous height when recursing
  • Re-searching downhill from every cell and timing out
  • Mixing up which borders belong to which ocean
Check your understanding

Why start from the oceans instead of from each land cell?

More in Graph DFS and BFS

#200Number of IslandsGrid flood fill#133Clone GraphGraph traversal with clone map#994Rotting OrangesMulti-source BFS (level-by-level)#127Word LadderShortest transformation via BFS#130Surrounded RegionsBorder-guarded flood fill#286Walls and GatesMulti-source BFS distance fill