417. Pacific Atlantic Water Flow

Problem¶

Given a height grid, water flows to an adjacent cell only if its height is no greater. Return every cell from which water can reach both the Pacific on the top or left edge and the Atlantic on the bottom or right edge.

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

Pacific: top/left
Atlantic: bottom/right
Output: [[0, 1], [1, 0], [1, 1]]

Key trick¶

Search backward from each ocean: from a cell, visit neighbors of equal or greater height. Cells reached by both searches are the answer.

Trap¶

Starting a traversal from every cell repeats work and can cost \(O(m^2n^2)\). Also, the reversed search must use >=, and visited cells are necessary because equal-height cells can form cycles.

Why is it interesting?¶

Reversing the graph turns many destination queries into two linear-time reachability searches.

Python solution¶

class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        m, n = len(heights), len(heights[0])
        directions = ((-1, 0), (1, 0), (0, -1), (0, 1))

        def flood(starts):
            # Reverse water flow: move from an ocean toward cells that are
            # at least as high as the current cell.
            seen = set(starts)
            stack = list(seen)

            while stack:
                r, c = stack.pop()

                for dr, dc in directions:
                    nr, nc = r + dr, c + dc

                    if (
                        0 <= nr < m
                        and 0 <= nc < n
                        and (nr, nc) not in seen
                        and heights[nr][nc] >= heights[r][c]
                    ):
                        seen.add((nr, nc))
                        stack.append((nr, nc))

            return seen

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

        pacific = flood(pacific_starts)
        atlantic = flood(atlantic_starts)

        # Row-major traversal gives deterministic output.
        return [
            [r, c]
            for r in range(m)
            for c in range(n)
            if (r, c) in pacific and (r, c) in atlantic
        ]

Time complexity: \(O(mn)\).

Space complexity: \(O(mn)\).

Comment on my solution¶

Your reachability logic is correct, including the positive-result memoization through reach_oceans.

The main issues are:

Running DFS independently from every cell costs up to \(O(m^2n^2)\).
Invalid cells are not memoized, so their searches may be repeated almost completely.
Recursive DFS can exceed Python's recursion limit on a grid containing a long path.
Finding both oceans only returns from the current recursive call, so earlier stack frames may continue unnecessary exploration.
Formatting spaces after commas and around tuple elements would improve readability.

Reversing the search removes the need to solve the same reachability problem once per cell.

# Ideas
# - this is a graph reachability problem with 3 constraints:
#   - movement (in fact it's a directed graph)
#     - be careful it can have cycle (2 adjacent cells with the same value)
#   - component touch 2 boundaries
#     - left or top and
#     - right and bottom
# - maybe start a bfs on each cell
#   - keep that cell if it can reach pacific and atlantic
#   - small optimization:
#     - during bfs if we pass through a cell that can reach boundaries,
#       that means that the starting cell can reach it too
#     - be careful, for a valid cell (starting the bfs), not all cells
#       visited during bfs can reach pacific and atlantic

# WORKS but slow
class Solution:
    def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]:
        m, n = len(heights), len(heights[0])

        reach_oceans = set()
        reach_pacific = False
        reach_atlantic = False
        visited = set()

        def dfs(start,r,c):
            nonlocal reach_pacific, reach_atlantic
            if (r,c) in reach_oceans:
                reach_oceans.add(start)
                return
            if r == 0 or c == 0:
                reach_pacific = True
            if r == m - 1 or c == n - 1:
                reach_atlantic = True
            if reach_pacific and reach_atlantic:
                reach_oceans.add(start)
                return
            for dr, dc in ((-1,0), (1,0), (0,-1), (0, 1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr,nc) not in visited and heights[nr][nc] <= heights[r][c]:
                    visited.add((nr,nc))
                    dfs(start, nr, nc)

        for r in range(m):
            for c in range(n):
                reach_pacific = False
                reach_atlantic = False
                visited = {(r,c)}
                dfs((r,c), r, c)
        return list(map(list,reach_oceans))