Graph Exploration Target: 15s
Reverse flow: DFS from ocean edges inward (uphill). Intersection of pacific-reachable and atlantic-reachable cells.
def pacificAtlantic(heights):
m, n = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visit, prev_h):
if (r, c) in visit or r < 0 or r >= m or c < 0 or c >= n:
return
if heights[r][c] < prev_h: return
visit.add((r, c))
for dr, dc in (0,1),(0,-1),(1,0),(-1,0):
dfs(r+dr, c+dc, visit, heights[r][c])
for c in range(n):
dfs(0, c, pac, 0) # top edge → pacific
dfs(m-1, c, atl, 0) # bottom edge → atlantic
for r in range(m):
dfs(r, 0, pac, 0) # left edge → pacific
dfs(r, n-1, atl, 0) # right edge → atlantic
return list(pac & atl)Type it from memory. Go.