AlgoMaster Logo

Pacific Atlantic Water Flow

Last Updated: March 28, 2026

medium
5 min read

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. The tricky part is that 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.

The key observation that makes this problem tractable: instead of asking "can water from this cell reach the ocean?", we can flip the question and 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 is equivalent to finding all 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

The most direct approach is to 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 works but is far too slow for larger grids. Many cells share the same reachability status, yet we rediscover it independently for every cell.

What if we ran the search from the oceans inward just once, marking every reachable cell in a single pass?

Approach 2: Reverse DFS from Ocean Borders (Optimal)

Intuition

Here is the key insight that transforms this problem. Instead of starting from each cell and asking "can water flow downhill to the ocean?", we flip the question: start from the ocean borders and ask "which cells can water flow from to reach here?" This is equivalent to starting at the ocean and moving to cells with equal or greater height, essentially flowing "uphill."

The Pacific touches the top row and left column. Any cell in the top row or left column can trivially reach the Pacific. Now, any neighbor of those border cells that has a height greater than or equal to the border cell can also reach the Pacific, because water would flow downhill from that neighbor to the border cell. We propagate this reachability inward using DFS.

We do the same thing for the Atlantic (starting from the bottom row and right column). At the end, any cell marked as reachable from both oceans is part of our answer. This reduces the problem to two traversals of the grid 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 cause a stack overflow on large grids. Can we achieve the same result with an iterative approach?

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.

BFS has a practical advantage over DFS here. Instead of relying on the call stack (which can overflow on large grids), BFS uses an explicit queue. This makes it safer for grids near the constraint limit of 200 x 200. The time and space complexity remain the same, but the iterative nature makes it more robust.

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