Pacific Atlantic Water Flow

Pacific Atlantic Water Flow

What is this problem about?

The Pacific Atlantic Water Flow problem gives you a matrix of heights representing an island. Water flows from higher or equal cells to lower. Find all cells from which water can flow to both the Pacific Ocean (top and left borders) and the Atlantic Ocean (bottom and right borders). This coding problem uses reverse BFS/DFS from both ocean borders. The array, matrix, BFS, and DFS interview pattern is the core.

Why is this asked in interviews?

Uber, Microsoft, Meta, Amazon, TikTok, Google, Bloomberg, and Adobe ask this classic grid BFS/DFS problem because it tests the "reverse flow" technique — instead of simulating water flowing down, flow water "up" from ocean borders. This elegantly handles the connectivity requirement. It's a canonical graph reachability problem on grids.

Algorithmic pattern used

Reverse BFS from both borders. Start BFS/DFS from all Pacific border cells (top row + left column). Mark all cells reachable (height ≥ neighbor) as "can reach Pacific." Similarly start from Atlantic borders (bottom row + right column) and mark "can reach Atlantic." Cells in both sets are the answer.

Example explanation

Matrix:

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

Pacific: water flows from top-left. Atlantic: from bottom-right. Cells reachable from both after reverse BFS: specific cells including (0,4),(1,3),(1,4),(2,2),(3,0),(3,1),(4,0). Answer = 7 cells (varies by exact matrix).

Common mistakes candidates make

• Forward simulation from each cell (O(n²*m²) — too slow).
• Not treating edges as multi-source starting points.
• Using >= for reverse flow (water flows to lower or equal neighbors — reverse means neighbor must be ≥ current to "flow up").
• Forgetting to add all border cells as starting points.

Interview preparation tip

Pacific Atlantic Water Flow is the canonical multi-source reverse BFS grid problem. Whenever a grid problem asks "find all cells that can reach a set of targets," reverse the flow direction and do multi-source BFS from the targets. Practice this reverse-BFS pattern on other problems: "cells that can reach the boundary," "flood fill from multiple sources." Two BFS passes and intersection is the clean approach.