• m == heights.length, n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 10⁵
• Water moves only up, down, left and right — never diagonally.
• Equal heights are passable in both directions.

Two words in this statement carry the difficulty: both and each. We need, for every cell on the island, an answer to two separate reachability questions. Notice what is not being asked — no distance, no shortest route, no count of steps. Just: can water get there at all? Keeping that straight decides which tool to use, and it is the first thing worth settling.

Take one cell, pour water on it, and follow every downhill route until you either fall off a Pacific edge, fall off an Atlantic edge, or run out of moves. Record whether each ocean was reached. Then repeat for the next cell.

def pacific_atlantic(heights):
    result = []
    for r in range(rows):
        for c in range(cols):
            if reaches_pacific(r, c) and reaches_atlantic(r, c):   # a full search each
                result.append([r, c])
    return result

It is correct, and it is quadratic. A single downhill exploration can sweep almost the whole island — picture a long descending ramp — so each of the m × n cells can cost up to m × n work, giving O((m × n)²). At the limit of 200 × 200 that is 40,000 cells each potentially touching 40,000 cells: 1.6 billion steps.

But the running time is not the most interesting problem with it. The repetition is. Consider two neighbouring cells that both drain toward the same valley. Their explorations trace nearly the same route, discover the same descent, and reach the same edge. Every cell on a mountainside re-derives the identical fact that the mountainside drains to the sea. The same downhill corridors are being walked over and over by different starting points, all heading toward the same handful of destinations.

That phrasing points at the fix, and it is the same move that rescues many-to-few problems generally: when thousands of searchers are converging on a few places, stop searching from the searchers and start searching from the places.

There are only two destinations that matter — the Pacific and the Atlantic. So instead of asking which cells drain into the Pacific, ask the mirror question: which cells can the Pacific reach if we walk backwards?

Reverse every rule. Water flows from a cell to a neighbour of equal or lower height. Traversed backwards, we move from a cell to a neighbour of equal or higher height. Start on the ocean's edge and climb.

The equivalence needs stating carefully, because it is the entire justification: a route from cell A down to the ocean exists if and only if the same sequence of cells, read in reverse, is a valid climb from the ocean up to A. Each individual step reverses cleanly — if height[X] is at least height[Y] then walking from Y to X is a legal uphill step — so a whole downhill route reverses into a whole uphill route, and vice versa. Nothing is lost or gained by the reversal; the two questions have exactly the same answer set.

So: start a single traversal seeded with every Pacific border cell at once, climb, and mark everything reachable. Every marked cell drains to the Pacific. Do the same from every Atlantic border cell. Then the cells appearing in both marked sets are the answer.

Seeding all border cells simultaneously rather than running one traversal per border cell is worth naming — it is a multi-source traversal, and it is not many searches but one search whose starting layer happens to have many members. Its cost is the same as a single search: each cell is claimed once, by whichever source reaches it, and since we only care whether a cell was reached and not from which source, having many origins costs nothing extra.

Two passes over the grid, each O(m × n), replaces 40,000 passes.

This is the question worth being deliberate about, because the earlier problems in this section all demanded breadth-first search and this one does not.

Breadth-first search expands in rings of equal distance, and that layered structure is what guarantees the first arrival at a cell is the shortest one. You need it exactly when the answer is a distance or a minimum number of steps.

Here the answer is neither. It is a yes-or-no about reachability. Whether a cell is reached in 3 steps or 30 makes no difference to the output, so the ordering guarantee that BFS pays for is worthless. Either traversal visits precisely the same set of cells and produces precisely the same answer.

Given the choice, depth-first search is usually the more comfortable fit: it is a few lines recursively, and it holds only the current route on the call stack rather than an entire frontier. The caveat is that the recursion depth can reach m × n on a long snaking path — 40,000 frames here, beyond Python's default limit — so an iterative version with an explicit stack, or BFS with a queue, is the safe choice at scale.

The decision rule to carry forward: asked for a shortest distance, use BFS; asked merely whether something is reachable, or asked to enumerate or count regions, either works and DFS is simpler.

def pacific_atlantic(heights):
    rows, cols = len(heights), len(heights[0])
    pacific, atlantic = set(), set()

    def climb(r, c, reached):
        reached.add((r, c))
        for nr, nc in ((r-1,c), (r+1,c), (r,c-1), (r,c+1)):
            if (0 <= nr < rows and 0 <= nc < cols
                    and (nr, nc) not in reached
                    and heights[nr][nc] >= heights[r][c]):    # uphill or level
                climb(nr, nc, reached)

    for c in range(cols):
        climb(0, c, pacific)                 # top edge touches the Pacific
        climb(rows - 1, c, atlantic)         # bottom edge touches the Atlantic
    for r in range(rows):
        climb(r, 0, pacific)                 # left edge touches the Pacific
        climb(r, cols - 1, atlantic)         # right edge touches the Atlantic

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

Each cell is added to each set at most once and inspects four neighbours, so the work is O(m × n) time with O(m × n) memory for the two sets.

A spiral, ascending from the 1 in the top-left corner around to the 9 in the middle.

The Pacific climb starts from the top row — (0,0)=1, (0,1)=2, (0,2)=3 — and the left column — (0,0)=1, (1,0)=8, (2,0)=7.

Pacific reaches everything except… let us list it: (0,0), (0,1), (0,2), (1,0), (2,0), (1,1), (1,2), (2,2), (2,1). That is the whole grid — the ascending spiral means every cell is climbable from the low corner.

The Atlantic climb starts from the bottom row — (2,0)=7, (2,1)=6, (2,2)=5 — and the right column — (0,2)=3, (1,2)=4, (2,2)=5.

The intersection drops (0,0) and (0,1), leaving (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2) — seven cells, matching the expected output.

The instructive case is (0,0), holding 1. It sits directly on the Pacific coast, so water there certainly reaches the Pacific. But it is the lowest cell on the island, hemmed in by 2 and 8, so no water can ever descend from it toward the Atlantic. Being low helps water arrive; it is being high that lets water leave. That inversion is exactly what makes the reverse traversal the natural framing.

Three things carry beyond this problem.

Reverse the arrows. When a question asks which of many starting points can reach a few destinations, flip it and search backwards from the destinations. The reversal is valid whenever each individual step is reversible under a mirrored rule — here, "flows to a lower-or-equal neighbour" becomes "climbs to a higher-or-equal neighbour". Check that reversibility explicitly; on a graph with genuinely one-way edges you must build the reverse adjacency first, and on a rule that is not cleanly invertible the trick simply fails.

Multi-source seeding. Many origins acting at once go into one traversal together, not into many traversals run in sequence. Whether the question is a distance from the nearest source or plain reachability, one pass suffices.

Compute each condition separately, then combine. The instinct on a "both A and B" question is to track both conditions inside a single traversal, which gets tangled fast — the routes to the two oceans are unrelated and a single walk cannot represent both. Running two independent traversals and intersecting the results is simpler to write and simpler to argue correct. Whenever a problem demands two independent properties of the same object, computing them in separate passes is usually the cleaner design.

Train the reflex: when a grid problem asks which cells can reach X, and X is small while the candidate cells are many, do not search from the cells. Sit on X, invert the movement rule, and let the search come to you.