Pacific Atlantic Water Flow

Q: Why is searching from the oceans so much cheaper?

There are only two targets but m * n sources. Searching from each source repeats the same regions over and over. Searching from each target once labels every cell in a single sweep per ocean.

mediumGraphs

You get an m x n grid heights describing land. The Pacific Ocean borders the top and left edges of the grid; the Atlantic Ocean borders the bottom and right edges.

Rain on a cell can flow to a neighbouring cell (up, down, left or right) whose height is less than or equal to the current cell's height. Any cell on an edge can also flow straight into the ocean on that edge.

Return the coordinates [r, c] of every cell from which water can reach both oceans, in any order.

Examples

Example 1

Input: heights = [[1, 3, 2], [4, 5, 1], [2, 1, 3]]

Output: [[0, 1], [0, 2], [1, 0], [1, 1], [2, 0]]

Explanation: The top-right and bottom-left corners touch both oceans. (0,1) reaches the Pacific directly and the Atlantic through (0,2). (1,0) reaches the Atlantic through (2,0). The peak (1,1) can flow anywhere. (0,0) is walled in by higher cells, so it only reaches the Pacific.

Example 2

Input: heights = [[1, 2], [4, 3]]

Output: [[0, 1], [1, 0], [1, 1]]

Explanation: (0,0) is lower than both neighbours, so its water only goes to the Pacific.

Hints

Approach

Search backwards from each ocean, moving uphill, and intersect the results.

Seed a Pacific search with every cell in the top row and left column. Seed an Atlantic search with every cell in the bottom row and right column.
Each search moves from a cell to a neighbour whose height is >= the current cell (the reverse of water flowing down), marking cells it reaches.
Return every cell marked by both searches.

Each search visits a cell at most once, so the total work is two passes over the grid. Note the direction flip: water flows to <=, so the reverse search climbs to >=. Getting that comparison backwards is the most common bug.

ComplexityTime O(m * n)Space O(m * n)

Python

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        rows, cols = len(heights), len(heights[0])
 
        def climb(starts: list[tuple[int, int]]) -> set[tuple[int, int]]:
            reached = set(starts)
            stack = list(reached)
            while stack:
                r, c = stack.pop()
                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 only
                        reached.add((nr, nc))
                        stack.append((nr, nc))
            return reached
 
        pacific = climb([(0, c) for c in range(cols)] + [(r, 0) for r in range(rows)])
        atlantic = climb([(rows - 1, c) for c in range(cols)] + [(r, cols - 1) for r in range(rows)])
        return [[r, c] for r in range(rows) for c in range(cols)
                if (r, c) in pacific and (r, c) in atlantic]

Follow-up questions

Return only the cells that reach exactly one ocean.
Water can only flow to strictly lower cells. Which comparison changes?

Frequently asked questions

There are only two targets but m * n sources. Searching from each source repeats the same regions over and over. Searching from each target once labels every cell in a single sweep per ocean.

Reversing a search so it starts from the few targets instead of the many sources is a common trick in dependency analysis. To find every service that can affect both of two critical systems, walk the dependency graph backwards from each critical system once and intersect, rather than tracing forward from every service.

Problem statement