The tell: Cells that can reach two destinations — easier solved backwards from each destination.
How you get there
1Searching forward from every cell is O(cells²).
2Instead search backwards from each ocean's border, moving only to equal-or-higher cells.
3The answer is the intersection of the two reachable sets.
Solution
Python
def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
if not heights:
return []
rows, cols = len(heights), len(heights[0])
pacific, atlantic = set(), set()
def dfs(r: int, c: int, seen: set, prev: int) -> None:
if (r, c) in seen or not (0 <= r < rows and 0 <= c < cols):
return
if heights[r][c] < prev: # water flows downhill, so walk uphill
return
seen.add((r, c))
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
dfs(r + dr, c + dc, seen, heights[r][c])
for c in range(cols):
dfs(0, c, pacific, heights[0][c])
dfs(rows - 1, c, atlantic, heights[rows - 1][c])
for r in range(rows):
dfs(r, 0, pacific, heights[r][0])
dfs(r, cols - 1, atlantic, heights[r][cols - 1])
return [list(cell) for cell in pacific & atlantic]
Time
O(rows · cols)
Space
O(rows · cols)
What goes wrong
Searching forward from every cell is correct but quadratic; reversing the direction is the insight.