Generated by Codex with GPT-5

Quick facts

What the problem is really asking

Each cell in the grid is a height. Water can flow from a cell to one of its four neighbors if the neighbor is at the same height or lower.

The Pacific touches the top and left edges. The Atlantic touches the bottom and right edges.

The goal is to return every cell from which water can eventually reach both oceans.

That is the part that usually trips people up. The problem is not asking for the shortest path, and it is not asking whether the oceans can reach each other. It is asking for the set of starting cells whose downhill paths can end at both boundaries.

The first idea most people try

A direct approach is to start from every cell, run a search outward, and see whether that search can reach the Pacific and the Atlantic.

That works logically, but it repeats a huge amount of work. Neighboring cells often explore almost the same downhill regions, so the same subproblems get solved again and again. In the worst case, that turns into roughly O((m * n)^2) work, which is much more than this problem needs.

The repeated overlap is the clue that the direction of thinking should change.

The key insight: reverse the flow

Instead of asking:

“From this cell, can water flow down to the ocean?”

ask the reverse question:

“Starting from the ocean border, which cells could have flowed into it?”

That reversal changes the traversal rule. In the original problem, water moves from high to low or equal height. In the reversed search, the traversal moves from low to high or equal height, because if cell A can flow to cell B, then a reverse search from B can move back to A.

So for a reverse traversal:

  • start from all Pacific-border cells and move only into neighbors with height greater than or equal to the current cell
  • do the same from all Atlantic-border cells
  • intersect the two reachable sets

Any cell visited by both reverse traversals is a cell whose water can flow to both oceans in the original direction.

How to derive the optimal solution in an interview

The clean derivation usually looks like this:

  1. Notice that brute force starts a search from every cell and repeats a lot of work.
  2. Observe that the ocean locations are fixed, while the candidate starting cells are many.
  3. Reverse the direction of the edges so the search begins from the oceans instead of every cell.
  4. Treat each ocean edge as a multi-source traversal, because every border cell touching that ocean is a valid starting point.
  5. Intersect the two visited sets to get the final answer.

This is the important mental move: when many sources point toward a small fixed set of sinks, it is often cheaper to run the search backward from the sinks.

Best approaches

There are two equally good high-level implementations:

  • reverse multi-source DFS
  • reverse multi-source BFS

Both visit each cell at most once per ocean, so both run in O(m * n) time and use O(m * n) extra space for the visited state.

The implementation below uses BFS because it is iterative, easy to reason about, and avoids Python recursion-depth issues on large grids. A DFS version is just as valid if recursion limits are not a concern.

Python solution

The implementation performs two multi-source BFS traversals:

  • one seeded with all Pacific-border cells
  • one seeded with all Atlantic-border cells

During each traversal, it only moves into neighbors that are at least as tall as the current cell. That is the reverse-flow condition.

from collections import deque
from typing import Deque, Iterable, List, Set, Tuple


Coordinate = Tuple[int, int]


def pacific_border_cells(row_count: int, column_count: int) -> List[Coordinate]:
    """Return all cells touching the Pacific without duplicating the top-left corner."""
    top_edge = [(0, column) for column in range(column_count)]
    left_edge = [(row, 0) for row in range(1, row_count)]
    return top_edge + left_edge


def atlantic_border_cells(row_count: int, column_count: int) -> List[Coordinate]:
    """Return all cells touching the Atlantic without duplicating the bottom-right corner."""
    bottom_edge = [(row_count - 1, column) for column in range(column_count)]
    right_edge = [(row, column_count - 1) for row in range(row_count - 1)]
    return bottom_edge + right_edge


def reverse_reachable_cells(
    heights: List[List[int]], start_cells: Iterable[Coordinate]
) -> Set[Coordinate]:
    """
    Run a reverse multi-source BFS from one ocean.

    From cell (r, c), the traversal may move to a neighbor only when that
    neighbor is at least as tall, because that neighbor could flow down into
    the current cell in the original problem direction.
    """
    row_count = len(heights)
    column_count = len(heights[0])
    visited: Set[Coordinate] = set(start_cells)
    frontier: Deque[Coordinate] = deque(visited)
    directions = ((1, 0), (-1, 0), (0, 1), (0, -1))

    while frontier:
        row, column = frontier.popleft()
        current_height = heights[row][column]

        for row_offset, column_offset in directions:
            next_row = row + row_offset
            next_column = column + column_offset

            if not (0 <= next_row < row_count and 0 <= next_column < column_count):
                continue

            next_cell = (next_row, next_column)
            if next_cell in visited:
                continue

            # Reverse-flow condition: climb only to equal-or-higher cells.
            if heights[next_row][next_column] < current_height:
                continue

            visited.add(next_cell)
            frontier.append(next_cell)

    return visited


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights or not heights[0]:
            return []

        row_count = len(heights)
        column_count = len(heights[0])

        pacific_reachable = reverse_reachable_cells(
            heights,
            pacific_border_cells(row_count, column_count),
        )
        atlantic_reachable = reverse_reachable_cells(
            heights,
            atlantic_border_cells(row_count, column_count),
        )

        shared_cells = pacific_reachable & atlantic_reachable

        # Return coordinates in row-major order for deterministic output.
        return [
            [row, column]
            for row in range(row_count)
            for column in range(column_count)
            if (row, column) in shared_cells
        ]

Why this works

The correctness hinges on one equivalence:

a cell can flow to an ocean in the original problem if and only if the reverse traversal from that ocean can reach the cell by walking only through equal-or-higher neighbors.

That statement is true because every legal downhill move in the original graph becomes a legal uphill-or-flat move in the reversed graph.

So after the Pacific traversal finishes, pacific_reachable contains exactly the cells that can drain into the Pacific. After the Atlantic traversal finishes, atlantic_reachable contains exactly the cells that can drain into the Atlantic.

The final answer must therefore be the intersection of those two sets. Nothing is missing, because every valid cell is reachable in both reverse searches. Nothing extra is included, because a cell only appears in the intersection if both oceans are reachable from it in the original direction.

Interview follow-ups

Could you implement the same idea with DFS instead of BFS?

Yes. The underlying idea does not change at all. The traversal is still multi-source, still starts from the ocean borders, and still follows the reverse-flow rule of moving only into equal-or-higher neighbors. A DFS implementation marks the same reachable set that BFS does, so the final intersection is identical. The main tradeoff is practical rather than algorithmic: recursive DFS is often shorter, but in Python a tall or adversarial grid can exceed the recursion limit. Iterative DFS or BFS avoids that risk while keeping the same O(m * n) time and O(m * n) space complexity.

Can you reduce the extra memory usage?

You cannot really beat O(m * n) auxiliary space in a meaningful way for the general version of this problem, because you must remember which cells were reached from which ocean. Also, the output itself can already contain O(m * n) coordinates. That said, the constant factors can be improved. Instead of keeping two Python sets of coordinate tuples, an implementation can use two boolean matrices, or even one integer matrix with bit flags such as 1 for Pacific and 2 for Atlantic. That keeps the same asymptotic complexity but reduces overhead and is often the best answer if the interviewer asks for a tighter implementation.

What if diagonal moves are also allowed?

The strategy still works. The only real change is the neighbor list. Instead of four directions, the traversal would consider eight directions, and the reverse-flow condition would remain the same: you may move from the current cell to a neighbor only if the neighbor height is at least the current height. The reason the solution survives this change is that the core graph reversal argument is unchanged. The complexity remains linear in the size of the grid up to a constant-factor increase, because each cell is still processed a bounded number of times and each cell now checks eight neighbors instead of four.

What if there are many different sink regions, not just two oceans?

The same pattern generalizes cleanly. For each sink region, run a multi-source traversal from all cells that belong to that region and record which cells can reach it in reverse. Then combine the reachability information according to the question being asked, such as cells that can reach all sinks or at least one sink. This works because the reverse-search interpretation is about reachability in a directed graph, not specifically about oceans. The tradeoff is that the total work scales with the number of sink groups. If there are k distinct sink sets, the straightforward version costs O(k * m * n) time and O(k * m * n) space unless the state is compressed.

Practical takeaway

This problem becomes much easier once it is seen as a graph-reversal problem instead of a search-from-every-cell problem.

The reusable pattern is:

  • identify a reachability question
  • reverse the direction of travel if the destinations are fixed and the sources are many
  • run multi-source traversals from the destinations
  • intersect or combine the visited sets

That pattern shows up well beyond this one matrix problem, which is why this question is worth learning deeply instead of just memorizing the final code.