I start two BFSs (or DFSs): one from all Pacific-border cells (top row + left column) and one from all Atlantic-border cells (bottom row + right column). For each search I only move from a cell to a neighbor if the neighbor's height is greater than or equal to the current cell's height (this simulates water flowing downhill from neighbor → current, so reversing the direction finds all cells that can flow to that ocean). Cells reachable by both searches can flow to both oceans.
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
if not heights or not heights[0]:
return []
m, n = len(heights), len(heights[0])
def bfs(starts):
visited = [[False] * n for _ in range(m)]
q = deque(starts)
for r, c in starts:
visited[r][c] = True
while q:
r, c = q.popleft()
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
# we can move to neighbor only if neighbor height >= current height
if heights[nr][nc] >= heights[r][c]:
visited[nr][nc] = True
q.append((nr, nc))
return visited
pacific_starts = [(0, j) for j in range(n)] + [(i, 0) for i in range(m)]
atlantic_starts = [(m-1, j) for j in range(n)] + [(i, n-1) for i in range(m)]
pacific_reach = bfs(pacific_starts)
atlantic_reach = bfs(atlantic_starts)
result = []
for i in range(m):
for j in range(n):
if pacific_reach[i][j] and atlantic_reach[i][j]:
result.append([i, j])
return result- Time: O(m * n)
- Space: O(m * n)
