Skip to main content

🟨 Pacific Atlantic Water Flow (#417)

🔗 Problem Link​

📋 Problem Statement​

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. Return a 2D list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

🔑 Key Insights & Approach​

Core Observation: DFS/BFS from ocean borders inward. Find cells reachable from both oceans.

Pattern: "Multi-source BFS/DFS" pattern.

🐍 Solution: Python​

from typing import List

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):
            visited.add((r, c))
            for dr, dc in [(0,1), (0,-1), (1,0), (-1,0)]:
                nr, nc = r + dr, c + dc
                if (0 <= nr < rows and 0 <= nc < cols and 
                    (nr, nc) not in visited and 
                    heights[nr][nc] >= heights[r][c]):
                    dfs(nr, nc, visited)
        
        for c in range(cols):
            dfs(0, c, pacific)
            dfs(rows-1, c, atlantic)
        
        for r in range(rows):
            dfs(r, 0, pacific)
            dfs(r, cols-1, atlantic)
        
        return list(pacific & atlantic)

📚 References​