Repository navigation
113 — Pacific Atlantic Water Flow
LeetCode 417 · Medium. There's an m x n rectangular island bordered by the Pacific Ocean (top and left edges) and the Atlantic Ocean (bottom and right edges). heights[r][c] is the height of cell (r, c). Water flows from a cell to an adjacent cell with height less than or equal to its own. Return the list of cells from which water can reach both oceans.
The obvious framing — "for each cell, can water starting there reach the Pacific, and separately, can it reach the Atlantic?" — means simulating outward flow from every single cell, which is expensive and repeats a huge amount of work (cells near the middle of the grid share almost their entire flow path). The trick that unlocks the efficient solution is running the problem backwards: instead of asking "where can water starting here go," start at the ocean borders and ask "which cells could water have come from to reach here?" Since "flows to a lower-or-equal neighbor" reverses into "came from a higher-or-equal neighbor," flooding inward from both oceans at once finds every reachable cell in a single pass each — and a cell qualifies for the final answer exactly when both floods reached it.
"Which cells can reach both of two specific borders/targets, following a directional flow rule" is the cue for reversing the traversal: instead of simulating forward from every candidate cell, flood inward from each target in a single multi-source BFS/DFS, using the inverse of the flow rule, then intersect the two reachable sets.
For every cell, simulate the flow rule outward, twice — once checking "can I reach a Pacific-border cell," once checking "can I reach an Atlantic-border cell" — each as its own independent traversal.
func pacificAtlanticBruteForce(_ heights: [[Int]]) -> [[Int]] {
let rows = heights.count
guard rows > 0 else { return [] }
let cols = heights[0].count
let dirs = [(1,0),(-1,0),(0,1),(0,-1)]
func canReach(_ startR: Int, _ startC: Int, isTarget: (Int, Int) -> Bool) -> Bool {
var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
var stack = [(startR, startC)]
visited[startR][startC] = true
if isTarget(startR, startC) { return true }
while let (r, c) = stack.popLast() {
for (dr, dc) in dirs {
let nr = r + dr, nc = c + dc
guard nr >= 0, nr < rows, nc >= 0, nc < cols, !visited[nr][nc] else { continue }
// Water flows FROM (r,c) TO (nr,nc) only if (nr,nc) is <= (r,c).
guard heights[nr][nc] <= heights[r][c] else { continue }
visited[nr][nc] = true
if isTarget(nr, nc) { return true }
stack.append((nr, nc))
}
}
return false
}
var result: [[Int]] = []
for r in 0..<rows {
for c in 0..<cols {
let reachesPacific = canReach(r, c) { rr, cc in rr == 0 || cc == 0 }
let reachesAtlantic = canReach(r, c) { rr, cc in rr == rows - 1 || cc == cols - 1 }
if reachesPacific && reachesAtlantic {
result.append([r, c])
}
}
}
return result
}Big-O: O((m·n)²) — a fresh O(m·n) traversal is run from every one of the m·n cells, twice.
Reverse the flow: flood inward from all Pacific-border cells at once (one multi-source BFS), and separately from all Atlantic-border cells at once, using the reversed rule — a neighbor qualifies if its height is >= the current cell's height, since that's the direction water could have flowed from.
func pacificAtlantic(_ heights: [[Int]]) -> [[Int]] {
let rows = heights.count
guard rows > 0 else { return [] }
let cols = heights[0].count
let dirs = [(1,0),(-1,0),(0,1),(0,-1)]
var pacific = Array(repeating: Array(repeating: false, count: cols), count: rows)
var atlantic = Array(repeating: Array(repeating: false, count: cols), count: rows)
func bfs(from starts: [(Int, Int)], _ reachable: inout [[Bool]]) {
var queue = starts
for (r, c) in starts { reachable[r][c] = true }
var head = 0
while head < queue.count {
let (r, c) = queue[head]
head += 1
for (dr, dc) in dirs {
let nr = r + dr, nc = c + dc
guard nr >= 0, nr < rows, nc >= 0, nc < cols, !reachable[nr][nc] else { continue }
guard heights[nr][nc] >= heights[r][c] else { continue }
reachable[nr][nc] = true
queue.append((nr, nc))
}
}
}
var pacificStarts: [(Int, Int)] = []
var atlanticStarts: [(Int, Int)] = []
for r in 0..<rows {
pacificStarts.append((r, 0))
atlanticStarts.append((r, cols - 1))
}
for c in 0..<cols {
pacificStarts.append((0, c))
atlanticStarts.append((rows - 1, c))
}
bfs(from: pacificStarts, &pacific)
bfs(from: atlanticStarts, &atlantic)
var result: [[Int]] = []
for r in 0..<rows {
for c in 0..<cols {
if pacific[r][c] && atlantic[r][c] {
result.append([r, c])
}
}
}
return result
}
// smoke test
let heights: [[Int]] = [
[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]
]
print(Set(pacificAtlantic(heights)).count) // 7Big-O: O(m·n) time — each border-flood visits every cell at most once, and there are only two floods total. O(m·n) space for the two reachability grids.
The brute force asks the same question m·n times, from scratch, in the wrong direction — forward flow simulation from each cell, which redoes an enormous amount of shared traversal work. The optimal solution flips the direction of the question: instead of "can this cell's water reach the ocean," it asks "which cells could send water to the ocean's edge, one hop at a time, working backward." Multi-source BFS from all border cells of one ocean at once means every cell is discovered by at most one flood per ocean — no repeats, no redundant re-traversal. The final answer is just the intersection of two boolean grids computed once each, instead of 2·m·n independent forward simulations.
- Graphs — the grid's implicit adjacency and the "flood inward from multiple sources" technique are the same multi-source BFS idea covered there.
-
BFS —
bfs(from:_:)is a textbook multi-source BFS: seed the queue with every starting cell at once instead of just one. -
Matrix Traversal — the bounds-checked four-directional walk is identical to every other grid problem in this chapter; only the qualifying condition (
>=instead of<=) changes.
Pacific Atlantic Water Flow is BFS run backward — flood inward from both oceans' borders at once using the reversed flow rule, and keep every cell both floods touched.
- Why does reversing "flows to a lower-or-equal neighbor" produce "came from a higher-or-equal neighbor" — walk through a concrete pair of adjacent heights to convince yourself the inequality really does flip correctly.
- Why does seeding the BFS queue with every border cell of an ocean at once (rather than running one BFS per border cell and unioning the results) still produce the correct reachable set, and why is it faster?
- A cell on the Pacific border and the Atlantic border simultaneously (e.g., a corner cell) — does it need any BFS traversal at all to be marked reachable for both oceans? Where in the code does that get handled?
⬅️ Previous: Max Area of Island · Next: Surrounded Regions ➡️