leetcode-417 Pacific Atlantic Water Flow

[417] Pacific Atlantic Water Flow

Key Concept: Reverse Thinking + Multiple Source DFS/BFS - Instead of checking from each cell if it can reach both oceans, start from ocean edges and find all cells reachable from each ocean. Cells reachable from both are the answer.

Pattern: Reverse direction thinking often simplifies complex reachability problems.

# Given an m x n matrix of non-negative integers representing the height of
# each unit cell, where the Pacific ocean touches the left and top edges and
# the Atlantic ocean touches the right and bottom edges.
# Water can flow from a cell to adjacent cells with height equal or lower.
# Find all cells where water can flow to both the Pacific and Atlantic oceans.
#
# Example 1:
# Input: 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]]
# Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
#
# Constraints:
# m == heights.length
# n == heights[i].length
# 1 <= m, n <= 200
# 0 <= heights[i][j] <= 10^5

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

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

        def dfs(r, c, visited):
            # Mark cell as reachable from this ocean
            visited.add((r, c))

            # Explore all 4 directions
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                # Check bounds and if not visited
                if (0 <= nr < rows and 0 <= nc < cols and
                    (nr, nc) not in visited and
                    # Water flows to current cell from neighbor
                    # (neighbor height >= current height)
                    heights[nr][nc] >= heights[r][c]):
                    dfs(nr, nc, visited)

        # Start DFS from Pacific edges (top and left)
        for c in range(cols):
            dfs(0, c, pacific)  # Top edge
        for r in range(rows):
            dfs(r, 0, pacific)  # Left edge

        # Start DFS from Atlantic edges (bottom and right)
        for c in range(cols):
            dfs(rows - 1, c, atlantic)  # Bottom edge
        for r in range(rows):
            dfs(r, cols - 1, atlantic)  # Right edge

        # Find cells reachable from both oceans
        result = []
        for r in range(rows):
            for c in range(cols):
                if (r, c) in pacific and (r, c) in atlantic:
                    result.append([r, c])

        return result

# Time Complexity: O(m * n) - each cell visited at most twice
# Space Complexity: O(m * n) - for visited sets and recursion stack
#
# Key Insight: Reverse the flow direction!
# Instead of "can this cell reach oceans?"
# Ask "which cells can the oceans reach?"
# This converts a complex problem into two simple DFS/BFS searches