LeetCode 417 - Pacific Atlantic Water Flow

Given an m x n matrix of non-negative integers representing heights, this Medium graph problem asks for all grid coordinates where rainwater can flow to both the Pacific and Atlantic oceans. Instead of launching forward searches from every cell, I performed reverse depth-first searches (DFS) starting from the ocean coastlines upward in O(M × N) time.

---

Problem link and explanation

• Problem: 417. Pacific Atlantic Water Flow
• Summary: Rainwater flows from a cell to adjacent cells of equal or lower height. Return a list of grid coordinates from which water can reach both the Pacific (top/left) and Atlantic (bottom/right) oceans.

Simulating downward flow from each individual cell repeats work across overlapping paths, resulting in O((M × N)²) time. Reversing the perspective—starting at the ocean boundaries and moving only to adjacent cells of equal or higher elevation—ensures each cell is visited at most once per ocean.

---

Approach

Maintain two visited sets: pacific and atlantic.

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

def dfs(r, c, visited, prev_height):
    if r < 0 or r >= rows or c < 0 or c >= cols:
        return

    if (r, c) in visited or heights[r][c] < prev_height:
        return

    visited.add((r, c))

    dfs(r + 1, c, visited, heights[r][c])
    dfs(r - 1, c, visited, heights[r][c])
    dfs(r, c + 1, visited, heights[r][c])
    dfs(r, c - 1, visited, heights[r][c])

1. Reverse DFS: If heights[r][c] < prev_height, water cannot flow upward from the ocean, so prune the branch. Otherwise, mark (r, c) in visited and traverse its 4 neighbors.
2. Pacific boundary start: Run DFS from every cell on the top row (r = 0) and left column (c = 0).
3. Atlantic boundary start: Run DFS from every cell on the bottom row (r = rows - 1) and right column (c = cols - 1).
4. Set intersection: Coordinates reachable by both oceans are obtained directly via set intersection (pacific & atlantic).

---

Complexity analysis

• Time complexity: O(M × N)
  • Each cell is visited at most once during the Pacific traversal and once during the Atlantic traversal.
• Space complexity: O(M × N)
  • Visited sets and recursion stack frames scale with matrix size in the worst case.

---

Implementation code

class Solution:

    def pacificAtlantic(self, heights):
        if not heights or not heights[0]:
            return []

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

        def dfs(r, c, visited, prev_height):
            if r < 0 or r >= rows or c < 0 or c >= cols:
                return

            if (r, c) in visited or heights[r][c] < prev_height:
                return

            visited.add((r, c))

            dfs(r + 1, c, visited, heights[r][c])
            dfs(r - 1, c, visited, heights[r][c])
            dfs(r, c + 1, visited, heights[r][c])
            dfs(r, c - 1, visited, heights[r][c])

        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])

        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])

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

---

Summary and reflection

Reversing the search direction from target boundaries to source cells dramatically simplifies state propagation. Expressing the final answer as a set intersection (pacific & atlantic) cleanly decouples the two independent reachability checks.