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

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

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment