Pacific Atlantic Water Flow

You are given a rectangular island heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The islands borders the Pacific Ocean from the top and left sides, and borders the Atlantic Ocean from the bottom and right sides.

Water can flow in four directions (up, down, left, or right) from a cell to a neighboring cell with height equal or lower. Water can also flow into the ocean from cells adjacent to the ocean.

Find all cells where water can flow from that cell to both the Pacific and Atlantic oceans. Return it as a 2D list where each element is a list [r, c] representing the row and column of the cell. You may return the answer in any order.

Approach

Reverse the flow: start DFS/BFS from the Pacific border and mark all cells that can reach it by moving to equal-or-higher heights. Do the same from the Atlantic border. Cells reachable in both searches are the answer.

Why It Works

Water can flow from cell A to B if B is lower or equal. Reversing the direction, we can move from ocean borders to any cell that is higher or equal, which means that cell can reach the ocean in the original direction. The intersection of Pacific-reachable and Atlantic-reachable cells is exactly the set of cells that can reach both oceans.

Complexity

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

Reference Implementation (Python)

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights or not heights[0]:
            return []
        rows, cols = len(heights), len(heights[0])
        pac = [[False] * cols for _ in range(rows)]
        atl = [[False] * cols for _ in range(rows)]

        def dfs(r: int, c: int, visited: List[List[bool]]):
            visited[r][c] = True
            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:
                    if not visited[nr][nc] and heights[nr][nc] >= heights[r][c]:
                        dfs(nr, nc, visited)

        for c in range(cols):
            dfs(0, c, pac)
            dfs(rows - 1, c, atl)
        for r in range(rows):
            dfs(r, 0, pac)
            dfs(r, cols - 1, atl)

        result = []
        for r in range(rows):
            for c in range(cols):
                if pac[r][c] and atl[r][c]:
                    result.append([r, c])
        return result