Pacific Atlantic Water Flow
Given heights[r][c], return coordinates from which water can flow to both Pacific (top/left) and Atlantic (bottom/right). Water flows to equal-or-lower neighbors.
Answers use simple, clear English.
Quick interview answer
Multi-source DFS/BFS inland from Pacific borders and from Atlantic borders following non-decreasing height. Intersection of reachable sets is the answer.
Detailed answer
Multi-source DFS/BFS inland from Pacific borders and from Atlantic borders following non-decreasing height. Intersection of reachable sets is the answer. Searching outward from each cell is too slow; reverse the flow from oceans.
Full explanation
Searching outward from each cell is too slow; reverse the flow from oceans.
Real example & use case
Flood-risk planning: parcels that can drain toward two coastlines under gravity constraints.
Pros & cons
Pros: O(m*n) reverse search. Cons: careful border seeding; visited sets needed.
Code example
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
if not heights: return []
R, C = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, seen):
seen.add((r, c))
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen and heights[nr][nc] >= heights[r][c]:
dfs(nr, nc, seen)
for c in range(C):
dfs(0, c, pac); dfs(R - 1, c, atl)
for r in range(R):
dfs(r, 0, pac); dfs(r, C - 1, atl)
return [list(p) for p in pac & atl]Practice code · python (view only · no execution)
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
if not heights: return []
R, C = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, seen):
seen.add((r, c))
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and (nr, nc) not in seen and heights[nr][nc] >= heights[r][c]:
dfs(nr, nc, seen)
for c in range(C):
dfs(0, c, pac); dfs(R - 1, c, atl)
for r in range(R):
dfs(r, 0, pac); dfs(r, C - 1, atl)
return [list(p) for p in pac & atl]