DIRS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def pacific_atlantic(heights):
if not heights:
return []
m, n = len(heights), len(heights[0])
pac, atl = set(), set()
def dfs(r, c, visited, prev):
if r < 0 or c < 0 or r >= m or c >= n:
return
if (r, c) in visited or heights[r][c] < prev:
return
visited.add((r, c))
for dr, dc in DIRS:
dfs(r + dr, c + dc, visited, heights[r][c])
for r in range(m):
dfs(r, 0, pac, 0)
dfs(r, n - 1, atl, 0)
for c in range(n):
dfs(0, c, pac, 0)
dfs(m - 1, c, atl, 0)
return [list(cell) for cell in pac & atl]Variables
m- number of rows in the gridn- number of columns in the grid
Explanation
Two DFS traversals from the borders, each visiting every cell at most once - **O(m · n)** time. Both visited sets together hold up to `m · n` cells, and recursion stack matches; **O(m · n)** auxiliary.