Pacific Atlantic Water Flow — InterviewPrepKit

Solving tips

Key insight: don't search forward from every cell (O((m*n)^2)); reverse the flow and search inland from each ocean's border once, then intersect the two reachable sets.
On the reversed climb, step to a neighbor only when its height is >= current (the reverse of downhill flow); use <= / >= so equal heights are passable both ways.
Seed a multi-source DFS/BFS with all border cells of an ocean at once, giving O(m*n) time and space per ocean.
Pitfall: corner cells legitimately belong to both oceans' borders, so seed all four edges; the answer is the intersection of the Pacific-reachable and Atlantic-reachable sets.

Problem

You’re given an m x n grid heights where heights[r][c] is the height of a cell. The Pacific Ocean touches the top edge and the left edge of the grid; the Atlantic Ocean touches the bottom edge and the right edge.

Water can flow from a cell to a neighbor (up/down/left/right) if the neighbor’s height is less than or equal to the current cell’s height. Water can flow off the grid into an ocean from any cell on that ocean’s border.

Return a list of all cells [r, c] from which water can reach both the Pacific and the Atlantic.

Examples

heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] → [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] — each listed cell can drain to both oceans (order may vary).
heights = [[1]] → [[0,0]] — a single cell touches every border, so it reaches both oceans.
heights = [[2,1],[1,2]] → [[0,0],[0,1],[1,0],[1,1]] — every cell can reach both oceans here.

Constraints

1 <= m, n <= 200
0 <= heights[r][c] <= 10^5
“Flow” is allowed to an equal-or-lower neighbor; ties count.

Think about it first

Hint 1

Doing a separate search from every cell to test "can this reach the ocean?" is O((m·n)²). Flip the question: instead of water flowing *down and out*, imagine it climbing *inland from each ocean*.

Hint 2

From an ocean's border cells, do a traversal that moves to a neighbor only if that neighbor is **higher or equal** (reverse of the real flow). Every cell you reach is a cell that could drain *into* that ocean. Run this once from the Pacific border and once from the Atlantic border.

Hint 3

You get two sets: cells reachable from the Pacific and cells reachable from the Atlantic. The answer is their intersection. Multi-source DFS or BFS seeded with all border cells at once does each ocean in one pass.

TL;DR

Reverse the flow: multi-source DFS/BFS inland from each ocean’s border, then intersect the two reachable sets — O(m·n) time, O(m·n) space.

Approach 1 — Brute force (search from every cell)

For each cell, run a DFS following the real flow (to equal-or-lower neighbors) and check whether it can touch a Pacific border and an Atlantic border.

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

        def reaches(sr: int, sc: int):
            seen = set()
            stack = [(sr, sc)]
            pac = atl = False
            while stack:
                r, c = stack.pop()
                if (r, c) in seen:
                    continue
                seen.add((r, c))
                if r == 0 or c == 0:
                    pac = True
                if r == m - 1 or c == n - 1:
                    atl = True
                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 heights[nr][nc] <= heights[r][c]:
                        stack.append((nr, nc))
            return pac and atl

        for r in range(m):
            for c in range(n):
                if reaches(r, c):
                    result.append([r, c])
        return result

Complexity: a full O(m·n) search from each of the m·n cells → O((m·n)²) time. For a 200×200 grid that’s ~1.6 billion operations — too slow.

Approach 2 — Reverse flow, multi-source DFS (optimal)

The insight: “which cells can reach ocean X?” is answered in one sweep if you traverse backwards — start at ocean X’s border and step to a neighbor only when it is higher or equal, the reverse of downhill flow. Seed the search with all of that ocean’s border cells at once (multi-source). Do this for the Pacific and the Atlantic; the answer is the intersection of the two reachable sets. DFS explores each branch to its end before backtracking.

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

        def dfs(r: int, c: int, visited: set) -> None:
            visited.add((r, c))
            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]):   # climb inland
                    dfs(nr, nc, visited)

        for c in range(n):
            dfs(0, c, pacific)          # top row  -> Pacific
            dfs(m - 1, c, atlantic)     # bottom row -> Atlantic
        for r in range(m):
            dfs(r, 0, pacific)          # left col -> Pacific
            dfs(r, n - 1, atlantic)     # right col -> Atlantic

        return [[r, c] for r in range(m) for c in range(n)
                if (r, c) in pacific and (r, c) in atlantic]

Walkthrough (heights = [[1]]): the single cell (0,0) is on the top and left border → added to pacific; on the bottom and right border → added to atlantic. Intersection is {(0,0)} → [[0,0]].

Complexity: each cell is visited at most once per ocean → O(m·n) time, O(m·n) space for the two visited sets and recursion.

Approach 3 — Reverse flow, multi-source BFS

The insight: identical reverse-flow logic, but seed a queue with every border cell of an ocean and expand level by level. BFS is preferred when a 200×200 grid could push recursive DFS past Python’s recursion limit; DFS is preferred for its shorter code. Both are correct because we only need reachability, not shortest distance.

from collections import deque

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

        def bfs(sources) -> set:
            visited = set(sources)
            queue = deque(sources)
            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 < m and 0 <= nc < n
                            and (nr, nc) not in visited
                            and heights[nr][nc] >= heights[r][c]):
                        visited.add((nr, nc))
                        queue.append((nr, nc))
            return visited

        pac_sources = [(0, c) for c in range(n)] + [(r, 0) for r in range(m)]
        atl_sources = [(m - 1, c) for c in range(n)] + [(r, n - 1) for r in range(m)]
        pacific = bfs(pac_sources)
        atlantic = bfs(atl_sources)
        return [[r, c] for r, c in pacific & atlantic]

Complexity: O(m·n) time, O(m·n) space.

Common pitfalls

Searching forward from every cell. That’s O((m·n)²); the whole trick is to reverse the flow and search inland from the oceans once per ocean.
Wrong inequality on the reverse search. Real flow goes to lower-or-equal; the reversed climb goes to higher-or-equal. Flip it and you get the wrong set.
Forgetting the corners belong to both oceans’ borders. Seed all four edges; corner cells legitimately start in both sets.
Missing the equal-height case. Ties are passable in both directions — use <= / >=, not strict inequalities.

Pattern takeaway

When “can each source reach a target?” would cost a search per source, invert the graph and search from the targets — one multi-source traversal per target answers it for every cell at once. Seeding BFS/DFS with a whole set of starting cells (“multi-source”) is the reusable move; intersect the reachable sets when a cell must satisfy multiple targets.