Graphs · LC #417
Pacific Atlantic Water Flow
Find grid cells that can drain to both oceans by reversing the water-flow direction and BFS uphill from each ocean's border, then intersecting the two reachability sets.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
There is an `m x n` rectangular island with the Pacific Ocean touching its top and left edges, and the Atlantic Ocean touching its bottom and right edges. Water can flow to a neighbor (up/down/left/right) if the neighbor's height is less than or equal to the current cell's height. Return a list of grid coordinates where water can flow to **both** the Pacific and Atlantic oceans.
Sample I/O
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]]
Time: O(m×n) · Space: O(m×n)
Intuition
How to Think About It
Intuition
Forward flow (high→low from each cell) is expensive - O(m²n²). Reverse: treat each ocean border as a source and flood uphill (neighbor height ≥ current). Cells reachable uphill from the Pacific border can drain to the Pacific; same for Atlantic. The answer is the intersection of both reachable sets.
Core Concept
Multi-source BFS from ocean borders. Pacific sources: top row + left column. Atlantic sources: bottom row + right column. BFS moves to neighbors with height ≥ current (uphill in reverse). Intersect the two visited sets. Time: O(m × n).
When to use
When forward traversal from every cell is too slow - reverse the direction and use multi-source BFS from boundary nodes. Any problem requiring intersection of two reachability sets.
When NOT to use
When the grid has non-uniform adjacency or the flow rule is more complex than a simple height comparison. When only one ocean is required (single BFS suffices).
Key Insights
What to Know Cold
- The key insight is reversing the flow direction - instead of asking "where does water go?", ask "what can reach the ocean border going uphill?".
- Multi-source BFS initializes the queue with all border cells simultaneously, not one at a time.
- The uphill condition is height[neighbor] >= height[current] (not >, equality matters for flat regions).
- Intersection of two Sets (or two boolean arrays) gives the final answer.
- DFS works equally well; BFS is preferred to avoid stack overflow on large grids.
1 example
Worked Examples
Multi-source BFS from both ocean borders
5×5 height grid - find cells draining to both oceans.
BFS uphill from Pacific border; BFS uphill from Atlantic border; return intersection.
function pacificAtlantic(heights: number[][]): number[][] {
const m = heights.length, n = heights[0].length;
const bfs = (starts: [number, number][]) => {
const visited = new Set(starts.map(([r, c]) => `${r},${c}`));
const q = [...starts];
while (q.length) {
const [r, c] = q.shift()!;
for (const [dr, dc] of [[1,0],[-1,0],[0,1],[0,-1]]) {
const [nr, nc] = [r + dr, c + dc];
const key = `${nr},${nc}`;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited.has(key) && heights[nr][nc] >= heights[r][c]) {
visited.add(key); q.push([nr, nc]);
}
}
}
return visited;
};
const pac = bfs([...Array(m).keys()].map(i => [i, 0] as [number,number]).concat([...Array(n).keys()].map(j => [0, j] as [number,number])));
const atl = bfs([...Array(m).keys()].map(i => [i, n-1] as [number,number]).concat([...Array(n).keys()].map(j => [m-1, j] as [number,number])));
const res: number[][] = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (pac.has(`${i},${j}`) && atl.has(`${i},${j}`)) res.push([i, j]);
return res;
}Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Tests whether you can reframe an expensive forward-search problem as an efficient reverse-search problem. The "reverse direction" insight is the core of this problem.