Pacific Atlantic Water Flow — Reverse Multi-Source BFS Queue Pattern
Sanjeev SharmaAdvertisement
Problem Statement
You are given an m x n integer matrix heights representing the height of each unit cell in a continent. The Pacific Ocean touches the continent's left and top edges, and the Atlantic Ocean touches the right and bottom edges.
Water can only flow in four directions (up, down, left, right) from a cell to a neighboring cell with height less than or equal to the current cell's height. Water can flow into the ocean from any cell adjacent to the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
Constraints:
m == heights.length,n == heights[i].length1 <= m, n <= 2000 <= heights[r][c] <= 10^5
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 This Problem Matters
LeetCode 417 Pacific Atlantic Water Flow is a staple FAANG grid problem at Amazon, Google, Meta, and Apple. It tests whether you can recognize the "reverse traversal" trick — instead of asking "from each cell, can water reach both oceans?" (which costs roughly O(m squared times n squared)), you ask "from each ocean's border, which cells can reach me by climbing uphill?" The BFS queue pattern shines here because every cell is processed at most once per ocean.
The interview signal is high. The naive solution times out. The optimal solution requires you to flip your perspective, run two independent multi-source BFS traversals, and intersect the results. Recruiters love this because it cleanly separates candidates who memorize patterns from those who reason about graph traversal direction.
The Core Insight
Forward simulation is wasteful. From each of the m times n cells, running BFS or DFS to check whether you can reach both oceans gives O(m squared times n squared) in the worst case.
The reverse insight: water flows downhill, so reverse the relation. If we stand on the ocean and climb the continent uphill, every cell we can reach is a cell that can drain into that ocean. Run a multi-source BFS from all Pacific border cells (top row plus left column) climbing only to neighbors with greater than or equal height. Do the same from the Atlantic border (bottom row plus right column). The answer is the intersection of the two visited sets.
Each cell is enqueued at most twice (once per ocean), so the total time is O(m times n). The deque from collections gives O(1) appends and pops, which is exactly what BFS needs.
Visual Dry Run
Consider a 3 by 3 grid:
1 2 3
4 5 6
7 8 9Pacific borders: top row and left column — cells (0,0), (0,1), (0,2), (1,0), (2,0). Atlantic borders: bottom row and right column — cells (0,2), (1,2), (2,0), (2,1), (2,2).
Pacific BFS climbs uphill. Starting from the borders, it reaches all 9 cells because every neighbor of a Pacific border cell has height greater than or equal to the border cell's height in this monotonic grid. Same for Atlantic.
Intersection equals the entire grid. Visual confirmation: in a monotonically increasing grid where the top-left is the global minimum, water from any cell can drain to the top edge by going up-left, but actually only cells touching both perimeters drain to both oceans. The reverse BFS captures this by starting at the perimeters and climbing inward.
Solution (Optimal)
The deque-backed BFS is the cleanest formulation. We seed the queue with every border cell, run BFS while only stepping to neighbors with greater than or equal height, and return the intersection of the two visited sets.
from collections import deque
from typing import List
def pacificAtlantic(heights: List[List[int]]) -> List[List[int]]:
if not heights or not heights[0]:
return []
m, n = len(heights), len(heights[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def bfs(starts):
visited = set(starts)
queue = deque(starts)
while queue:
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if (0 <= nr < m and 0 <= nc < n
and (nr, nc) not in visited
and heights[nr][nc] >= heights[r][c]):
visited.add((nr, nc))
queue.append((nr, nc))
return visited
pacific_starts = [(0, c) for c in range(n)] + [(r, 0) for r in range(1, m)]
atlantic_starts = [(m - 1, c) for c in range(n)] + [(r, n - 1) for r in range(m - 1)]
return [list(cell) for cell in bfs(pacific_starts) & bfs(atlantic_starts)]function pacificAtlantic(heights) {
if (!heights.length || !heights[0].length) return [];
const m = heights.length, n = heights[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const bfs = (starts) => {
const visited = new Set(starts.map(([r, c]) => r * n + c));
const queue = [...starts];
let head = 0;
while (head < queue.length) {
const [r, c] = queue[head++];
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
const key = nr * n + nc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n
&& !visited.has(key)
&& heights[nr][nc] >= heights[r][c]) {
visited.add(key);
queue.push([nr, nc]);
}
}
}
return visited;
};
const pac = [], atl = [];
for (let c = 0; c < n; c++) { pac.push([0, c]); atl.push([m - 1, c]); }
for (let r = 0; r < m; r++) { pac.push([r, 0]); atl.push([r, n - 1]); }
const p = bfs(pac), a = bfs(atl);
const result = [];
for (const key of p) if (a.has(key)) result.push([Math.floor(key / n), key % n]);
return result;
}Complexity. Time O(m times n) — each cell enters each BFS queue at most once. Space O(m times n) for the visited sets and queues.
Common Mistakes
- Running forward BFS from every cell. This is O((m times n) squared) in the worst case and times out on large grids.
- Using a strict greater-than comparison. Water flows over equal heights, so the reverse climb must allow greater than or equal.
- Re-adding border cells in both row and column iteration, double-seeding the queue. Use a set or skip the corner overlap with a range starting at 1.
- Forgetting to mark a cell visited at enqueue time, only at dequeue. This causes duplicate work and incorrect counts in dense grids.
Interview Tips
- Start by describing the brute force and why it explodes. Recruiters want to see you reject it consciously.
- Pitch the reverse-BFS reframing out loud — "water flows downhill from continent to ocean, but I'll walk uphill from ocean to continent."
- Mention the queue choice. A deque with popleft is O(1); a Python list with pop(0) is O(n) and will TLE.
- Discuss why BFS and DFS both work here. BFS gives clearer iterative code without recursion depth concerns on 200 by 200 grids.
- If asked, derive the time bound: each cell enqueued at most twice, four neighbor checks each, totaling O(8 times m times n) which simplifies to O(m times n).
Follow-up Questions
- What if water can also flow diagonally? Add four diagonal directions to the dirs array. Complexity stays O(m times n).
- What if you must return only the count, not coordinates? Return the size of the intersection set; same complexity.
- What if heights can change over time and queries arrive online? This becomes a dynamic graph reachability problem; consider offline batching or recomputation thresholds.
- What if the grid is sparse and stored as a list of cells? Switch to a hash-based adjacency representation; BFS still works.
- How would you parallelize this for very large grids? The two ocean BFS runs are independent and embarrassingly parallel.
Key Takeaways
- Reverse BFS from boundaries is the canonical FAANG trick for "reach the edge" grid problems.
- A deque-backed BFS queue with O(1) popleft is non-negotiable for performance.
- Multi-source BFS just means seeding the queue with every starting cell up front.
- Marking cells visited at enqueue time, not dequeue time, is essential to avoid duplicate work.
- Time complexity is O(m times n), space is O(m times n) for visited bitmaps.
- The two BFS traversals are independent and parallelizable, a useful observation for distributed systems follow-ups.
Advertisement
