AlgoMaster Logo

Pacific Atlantic Water Flow

mediumFrequency7 min readUpdated June 23, 2026

Understanding the Problem

We have a grid where each cell has a height value. Water flows from a cell to its neighbor if the neighbor's height is less than or equal to the current cell's height. The Pacific Ocean borders the top row and leftmost column, while the Atlantic Ocean borders the bottom row and rightmost column.

We need to find every cell from which water can eventually reach both oceans. Water can flow through a chain of cells, not just directly to the border, so a cell in the middle of the grid might still reach both oceans if there exists a valid downhill (or equal height) path to each border.

A cleaner formulation reverses the direction of travel. Instead of asking "can water from this cell reach the ocean?", ask "which cells can the ocean reach if water flows uphill?" Starting from the ocean borders and moving to cells with equal or greater height finds exactly the set of cells that can drain to that ocean.

Key Constraints:

  • 1 <= m, n <= 200 -> The grid has at most 200 x 200 = 40,000 cells. An O(mn) solution per cell would give O((mn)^2) = 1.6 billion operations, which is too slow. We need O(m*n) total.
  • 0 <= heights[r][c] <= 10^5 -> Heights are non-negative integers. No special handling needed for negative values.

Approach 1: Brute Force (DFS from Every Cell)

Intuition

Check each cell individually. For every cell in the grid, run a DFS to see if water can flow from that cell to the Pacific Ocean, and another DFS to see if water can reach the Atlantic Ocean. If both searches succeed, include the cell in the result.

Water flows from a cell to a neighbor if the neighbor's height is less than or equal to the current cell's height. So our DFS follows a "downhill or flat" path. We track visited cells to avoid infinite loops.

Algorithm

  1. For each cell (r, c) in the grid:
    • Run a DFS to check if water can reach any Pacific border cell (top row or left column).
    • Run a DFS to check if water can reach any Atlantic border cell (bottom row or right column).
    • If both return true, add [r, c] to the result.
  2. Return the result list.

Example Walkthrough

1Check (0,0)=1: DFS downhill to Pacific border? YES (already on border). DFS to Atlantic? YES (path via row 3,4).
0
1
2
3
4
0
check
1
2
2
3
5
1
3
2
3
4
4
2
2
4
5
3
1
3
6
7
1
4
5
4
5
1
1
2
4
1/4

Code

This approach is too slow for larger grids. Many cells share the same reachability status, yet we rediscover it independently for every cell. The next approach computes reachability once by searching from the oceans inward.

Approach 2: Reverse DFS from Ocean Borders (Optimal)

Intuition

Instead of starting from each cell and asking "can water flow downhill to the ocean?", start from the ocean borders and ask "which cells can drain here?" That is the same as starting at the ocean and moving to cells with equal or greater height, flowing uphill.

The Pacific touches the top row and left column, so any cell in the top row or left column reaches the Pacific directly. A neighbor of a border cell with height greater than or equal to that border cell also reaches the Pacific, because water flows downhill from the neighbor to the border. We propagate this reachability inward using DFS.

We repeat this for the Atlantic, starting from the bottom row and right column. Any cell reachable from both oceans is part of the answer. This reduces the problem to two grid traversals instead of m * n traversals.

Algorithm

  1. Create two boolean matrices: pacific and atlantic, both of size m x n, initialized to false.
  2. Start DFS from all Pacific border cells (top row and left column). Mark each reachable cell in pacific as true. Move to a neighbor only if its height is greater than or equal to the current cell.
  3. Start DFS from all Atlantic border cells (bottom row and right column). Mark each reachable cell in atlantic as true. Same height condition.
  4. Iterate over all cells. If pacific[r][c] and atlantic[r][c] are both true, add [r, c] to the result.
  5. Return the result.

Example Walkthrough

1Initial grid. Pacific = top + left edges. Atlantic = bottom + right edges.
0
1
2
3
4
0
1
2
2
3
5
1
3
2
3
4
4
2
2
4
5
3
1
3
6
7
1
4
5
4
5
1
1
2
4
1/10

Code

The DFS approach uses recursion, which can overflow the call stack on large grids. The next approach replaces the recursion with an explicit queue.

Approach 3: BFS from Ocean Borders (Optimal, Iterative)

Intuition

This approach uses the same reverse-from-border strategy as Approach 2, but replaces the recursive DFS with an iterative BFS. The logic is identical: start from each ocean's border cells, explore neighbors with equal or greater height, and find the intersection.

The advantage is that BFS uses an explicit queue instead of the call stack, so a grid near the constraint limit of 200 x 200 cannot overflow the recursion depth. The time and space complexity are the same as the recursive version.

Algorithm

  1. Create two boolean matrices: pacific and atlantic.
  2. Initialize a queue with all Pacific border cells (top row + left column). Mark them as reachable. Run BFS: for each cell dequeued, check all four neighbors. If a neighbor has height >= current cell and has not been visited, mark it and add it to the queue.
  3. Do the same for Atlantic border cells (bottom row + right column).
  4. Collect all cells where both pacific[r][c] and atlantic[r][c] are true.

Example Walkthrough

1Seed Pacific queue with top row + left column. Seed Atlantic queue with bottom row + right column.
0
1
2
3
4
0
1
2
2
3
5
1
3
2
3
4
4
2
2
4
5
3
1
3
6
7
1
4
5
4
5
1
1
2
4
1/4

Code