Pacific Atlantic Water Flow

Problem

You have a grid of heights. The Pacific touches the top and left edges, the Atlantic touches the bottom and right edges. Water flows from a cell to a neighbor only if the neighbor's height is less than or equal to the current cell's. Return every cell from which water can reach both oceans.

Your signal — what pointed here?Your skeleton — the reusable shape

30 MIN00:00unlocks in 30:00

Signal

"Which cells can reach both of two borders" is a multi-source reachability problem — but simulating water flow forward from every single cell would be O((rows·cols)²). The trick: reverse the direction and flood fill inward from each ocean's border cells, moving to neighbors that are equal or higher (since that's the reverse of "water flows downhill to me").

Approach

Run one multi-source BFS/DFS starting from all Pacific-border cells at once, moving to a neighbor whenever the neighbor's height is >= the current cell's — this marks every cell water could have flowed down from to reach the Pacific. Do the same, separately, from all Atlantic-border cells. A cell belongs to the answer exactly when it's marked reachable in both passes.

Skeleton

pacific = multi_source_bfs(top_row + left_col, move if neighbor_height >= current)
atlantic = multi_source_bfs(bottom_row + right_col, move if neighbor_height >= current)
return [cell for cell in pacific if cell in atlantic]

Solution

from collections import deque


def pacific_atlantic(heights: list[list[int]]) -> list[list[int]]:
    rows, cols = len(heights), len(heights[0])

    def bfs(starts: list[tuple[int, int]]) -> set[tuple[int, int]]:
        reachable = set(starts)
        queue = deque(starts)
        while queue:
            r, c = queue.popleft()
            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 (nr, nc) not in reachable
                    and heights[nr][nc] >= heights[r][c]
                ):
                    reachable.add((nr, nc))
                    queue.append((nr, nc))
        return reachable

    pacific_starts = [(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)]
    atlantic_starts = [(rows - 1, c) for c in range(cols)] + [
        (r, cols - 1) for r in range(rows)
    ]

    pacific = bfs(pacific_starts)
    atlantic = bfs(atlantic_starts)

    return [[r, c] for r, c in pacific & atlantic]

Complexity

O(rows · cols) time — each ocean's BFS visits every cell at most once, and two BFS passes plus a set intersection stay linear in grid size. O(rows · cols) space for the two reachable sets.

Pitfalls

Getting the inequality backwards — moving to a neighbor when it's <= current (the forward flow direction) instead of >= breaks the reversal and gives the wrong reachable set.
Simulating flow forward from every cell individually is correct but O((rows·cols)²) — the reversed multi-source BFS is what makes this linear, and is the whole point of the problem.
Corner cells belong to both border lists — seeding the BFS queue with a plain list (not deduping) is harmless since reachable already guards re-visits, but double-check your start-set construction doesn't silently miss a border.

locked30:00 left