Pacific Atlantic Water Flow

Problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island’s left and top edges, and the Atlantic Ocean touches the island’s right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell’s height is less than or equal to the current cell’s height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) 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]]
Explanation: Water can flow to both oceans from the cells marked.

Example 2:

Input: heights = [[1]]
Output: [[0,0]]
Explanation: Water can flow from the only cell to both oceans.

Constraints:

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10^5

Solution

Approach: Reverse DFS from Ocean Borders

The key insight is to work backwards: start from ocean borders and find all cells that can reach each ocean, then find the intersection.

Implementation

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

        m, n = len(heights), len(heights[0])
        pacific = set()
        atlantic = set()

        def dfs(r, c, visited):
            visited.add((r, c))
            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

            for dr, dc in directions:
                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]):
                    dfs(nr, nc, visited)

        # DFS from Pacific borders (top and left)
        for i in range(m):
            dfs(i, 0, pacific)
        for j in range(n):
            dfs(0, j, pacific)

        # DFS from Atlantic borders (bottom and right)
        for i in range(m):
            dfs(i, n - 1, atlantic)
        for j in range(n):
            dfs(m - 1, j, atlantic)

        # Find intersection
        return list(pacific & atlantic)

Approach 2: BFS from Ocean Borders

from collections import deque

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

        m, n = len(heights), len(heights[0])

        def bfs(queue):
            visited = set(queue)
            while queue:
                r, c = queue.popleft()
                directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

                for dr, dc in directions:
                    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

        # Initialize queues with border cells
        pacific_queue = deque()
        atlantic_queue = deque()

        for i in range(m):
            pacific_queue.append((i, 0))
            atlantic_queue.append((i, n - 1))
        for j in range(n):
            pacific_queue.append((0, j))
            atlantic_queue.append((m - 1, j))

        pacific = bfs(pacific_queue)
        atlantic = bfs(atlantic_queue)

        return list(pacific & atlantic)

Complexity Analysis

Time Complexity: O(m * n), where m and n are grid dimensions. Each cell is visited at most twice (once for each ocean).
Space Complexity: O(m * n) for the visited sets.

Key Insights

Reverse Thinking: Instead of checking from each cell if it can reach both oceans, we start from oceans and find what can reach them.
Flow Direction: Water flows from high to low, so when working backwards, we move from low to high (heights[nr][nc] >= heights[r][c]).
Two Separate Searches: We perform separate DFS/BFS from Pacific and Atlantic borders, then find cells reachable from both.
Border Initialization: Pacific touches top and left edges, Atlantic touches bottom and right edges.
Set Intersection: The answer is the intersection of cells that can reach both oceans.