LeetCode Solutions Blog

Pacific Atlantic Water Flow

Number: 417

Difficulty: Medium

Paid? No

Problem Description

Given an m x n matrix representing heights of cells on an island, determine which cells can allow water to flow to both the Pacific and Atlantic oceans. The Pacific touches the left and top borders, while the Atlantic touches the right and bottom borders. Water can flow from a cell to its four neighbors if the neighbor’s height is less than or equal to the current cell's height.

Key Insights

Reverse the typical DFS/BFS perspective: start from the oceans and work inward.
Maintain two matrices (or sets) to keep track of cells reachable from the Pacific and Atlantic edges.
A cell can be added to the result if it is reached in both traversals.
The height constraint ensures water flows only in non-increasing order.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns. Each cell is processed up to twice (once from each ocean). Space Complexity: O(m * n) for the visited matrices and the recursion/queue used in DFS/BFS.

Solution

The solution uses depth-first search (DFS) from the ocean boundaries. We initialize two boolean matrices, one for each ocean. For the Pacific, we start DFS from the leftmost column and top row; for the Atlantic, we start from the rightmost column and bottom row. In each DFS, if the next cell has a height equal to or greater than the current cell and hasn’t been visited, we continue the search. Finally, we scan through the grid to collect cells that are reachable from both oceans. This reverse search simplifies the path validations and leverages the allowed water flow conditions.

Code Solutions

# Python solution for Pacific Atlantic Water Flow

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])
        pacific_reachable = [[False for _ in range(cols)] for _ in range(rows)]
        atlantic_reachable = [[False for _ in range(cols)] for _ in range(rows)]
        
        # Directions: up, down, left, right
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        # DFS function to mark reachable cells
        def dfs(r, c, reachable):
            reachable[r][c] = True
            for dr, dc in directions:
                new_r, new_c = r + dr, c + dc
                # Check bounds and conditions to flow water
                if (0 <= new_r < rows and 0 <= new_c < cols and 
                    not reachable[new_r][new_c] and 
                    heights[new_r][new_c] >= heights[r][c]):
                    dfs(new_r, new_c, reachable)
        
        # DFS from Pacific ocean borders (top row and left column)
        for i in range(rows):
            dfs(i, 0, pacific_reachable)
        for j in range(cols):
            dfs(0, j, pacific_reachable)
        
        # DFS from Atlantic ocean borders (bottom row and right column)
        for i in range(rows):
            dfs(i, cols - 1, atlantic_reachable)
        for j in range(cols):
            dfs(rows - 1, j, atlantic_reachable)
        
        # Collect cells that can reach both oceans
        result = []
        for r in range(rows):
            for c in range(cols):
                if pacific_reachable[r][c] and atlantic_reachable[r][c]:
                    result.append([r, c])
        return result