# LeetCode 417: Pacific Atlantic Water Flow — Step-by-Step Visual Trace

**Medium** — Graph | DFS | Matrix | Backtracking

## The Problem

Find all cells in a 2D matrix where rainwater can flow to both the Pacific Ocean (left and top edges) and Atlantic Ocean (right and bottom edges), where water flows from higher or equal height cells to lower or equal height cells.

## Approach

Use reverse DFS starting from ocean boundaries to find all cells reachable by each ocean. Start DFS from Pacific edges (top row and left column) and Atlantic edges (bottom row and right column), then find the intersection of cells reachable by both oceans.

**Time:** O(m * n) · **Space:** O(m * n)

## Code

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

        rows, cols = len(heights), len(heights[0])
        pacific_reachable = set()
        atlantic_reachable = set()

        def dfs(r, c, reachable):
            reachable.add((r, c))
            for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                nr, nc = r + dr, c + dc
                if (
                    0 <= nr < rows
                    and 0 <= nc < cols
                    and (nr, nc) not in reachable
                    and heights[nr][nc] >= heights[r][c]
                ):
                    dfs(nr, nc, reachable)

        for r in range(rows):
            dfs(r, 0, pacific_reachable)
            dfs(r, cols - 1, atlantic_reachable)

        for c in range(cols):
            dfs(0, c, pacific_reachable)
            dfs(rows - 1, c, atlantic_reachable)

        return list(pacific_reachable & atlantic_reachable)
```

## Watch It Run

> **[Open interactive visualization](https://tracelit.dev/app?trace=0417_pacific-atlantic-water-flow)**

> **Try it yourself:** Open [TraceLit](https://tracelit.dev/app?trace=0417_pacific-atlantic-water-flow) and step through every line.

---

*Built with [TraceLit](https://tracelit.dev) — the visual algorithm tracer for LeetCode practice.*