LeetCode 417: Pacific Atlantic Water Flow (Reverse BFS)
Reverse multi-source BFS from both oceans to get an O(mn) solution.
This is a solution to LeetCode 417 — Pacific Atlantic Water Flow
Intuition#
The statement “Water can flow from any cell adjacent to an ocean into the ocean” suggests that to determine whether a cell can reach an ocean, we only need to check whether it can reach the coastline.
Viewed as a graph problem, each cell is a node and there is a directed edge from A to B when A and B are adjacent and height(A) >= height(B). The task becomes finding all nodes that can reach any coastline node.
However, explicitly building an adjacency matrix is wasteful for large grids (up to 200×200). A simpler and more efficient idea is to reverse the search: instead of asking which nodes can reach the coast, start from the coast and explore inward. In the reversed graph, every node reachable from the coast corresponds to a node that can flow to that coast in the original graph. So we can run a flood fill from each ocean’s coast and mark all cells reachable under the non-decreasing-height constraint.
Approach#
Run BFS or DFS from all coast cells for each ocean — once for the Pacific and once for the Atlantic. The answers are the cells that are reachable from both searches (intersection of the two reachable sets).
Code#
from collections import deque
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
if not heights or not heights[0]:
return []
rows, cols = len(heights), len(heights[0])
if rows == 1 or cols == 1:
return [[i, j] for i in range(rows) for j in range(cols)]
def bfs(starts):
q = deque(starts)
seen = [[False]*cols for _ in range(rows)]
for r, c in starts:
seen[r][c] = True
while q:
r, c = q.popleft()
h = heights[r][c]
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and not seen[nr][nc] and heights[nr][nc] >= h:
seen[nr][nc] = True
q.append((nr, nc))
return seen
pac_starts = [(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)]
atl_starts = [(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)]
pac_seen = bfs(pac_starts)
atl_seen = bfs(atl_starts)
res = [[r, c] for r in range(rows) for c in range(cols) if pac_seen[r][c] and atl_seen[r][c]]
return res