LeetCode 417: Pacific Atlantic Water Flow Solution in Python – A Step-by-Step Guide

What Is LeetCode 417: Pacific Atlantic Water Flow?

In LeetCode 417: Pacific Atlantic Water Flow, you’re given an m × n grid heights where each cell’s value is its height (e.g., [[1,2,2],[3,2,3],[2,3,1]]). Water flows from a cell to an adjacent one (up, down, left, right) if the neighbor’s height is less than or equal to the current cell’s height. The Pacific Ocean borders the top and left edges, and the Atlantic Ocean borders the bottom and right edges. Your task is to return a list of coordinates [r, c] where water can flow to both oceans. For example, in the 3×3 grid above, water from [1,0] (3) can reach both, yielding [[0,2],[1,0],[1,1],[2,0],[2,1]].

Problem Statement

• Input: An m × n integer matrix heights.
• Output: A list of lists—coordinates [r, c] where water flows to both Pacific and Atlantic.
• Rules:
• Water flows to adjacent cells (up, down, left, right) if height ≤ current height.
• Pacific: top (row 0) and left (col 0).
• Atlantic: bottom (row m-1) and right (col n-1).

Constraints

• m == heights.length.
• n == heights[i].length.
• 1 <= m, n <= 200.
• 0 <= heights[r][c] <= 10⁵.

Examples

• 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]].
• Input: heights = [[1,2,3],[4,5,6],[7,8,9]]
• Output: [[0,2],[1,1],[1,2],[2,0],[2,1],[2,2]].
• Input: heights = [[1]]
• Output: [[0,0]] (single cell reaches both).

Understanding the Problem: Tracing Water Flow

To solve LeetCode 417: Pacific Atlantic Water Flow in Python, we need to find cells where water can flow to both the Pacific (top/left) and Atlantic (bottom/right) edges. A brute-force idea might be to simulate water flow from every cell—but with up to 200×200 cells, that’s too slow! Instead, we’ll use:

• Best Solution (DFS from Borders): O(mn) time, O(mn) space—flows inward from oceans.
• Alternative Solution (BFS with Queues): O(mn) time, O(mn) space—queues the exploration.

Let’s dive into the DFS solution with a clear, step-by-step explanation.

Best Solution: DFS from Borders

Why This Is the Best Solution

The DFS from borders method is the top pick because it’s efficient—O(mn) time, O(mn) space—and cleverly reverses the problem. Instead of flowing water out from each cell, it starts at the ocean borders and flows inward to cells that can reach them, using DFS to mark reachable spots. It’s like letting the oceans flood the land and seeing where they meet!

How It Works

Think of the grid as a map with rivers flowing uphill:

• Step 1: Set Up Tracking:
• Two sets: pacific (cells reaching Pacific), atlantic (cells reaching Atlantic).
• Step 2: Flood from Borders:
• DFS from top/left edges to fill pacific.
• DFS from bottom/right edges to fill atlantic.
• Flow to neighbors if height ≥ current (water flows downhill or level).
• Step 3: Find Overlap:
• Intersection of pacific and atlantic = cells reaching both.
• Step 4: Why This Works:
• Starting at borders ensures all reachable cells are found.
• DFS explores efficiently, marking paths in one pass.
• It’s like flooding from the edges and spotting the high ground where waters collide!

Step-by-Step Example

Example: heights = [[1,2,3],[4,5,6],[7,8,9]]

• Grid:

1 2 3 4 5 6 7 8 9

• Pacific DFS:
• Start: (0,0)=1, (0,1)=2, (0,2)=3, (1,0)=4, (2,0)=7.
• From (0,0): Up/down/left out, right (0,1)=2≥1, DFS: (0,2)=3≥2, (1,1)=5≥2.
• From (0,1): (1,1)=5≥2.
• From (2,0): (1,0)=4≤7, (2,1)=8≥7.
• Pacific: {(0,0), (0,1), (0,2), (1,0), (1,1), (2,0), (2,1)}.
• Atlantic DFS:
• Start: (0,2)=3, (1,2)=6, (2,2)=9, (2,0)=7, (2,1)=8.
• From (2,2): Up (1,2)=6≤9, left (2,1)=8≤9, DFS: (1,1)=5≤6, (2,0)=7≤8.
• Atlantic: {(0,2), (1,1), (1,2), (2,0), (2,1), (2,2)}.
• Overlap: {(0,2), (1,1), (2,0), (2,1)}.
• Result: [[0,2], [1,1], [2,0], [2,1]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so you can follow every step:

Copy codeclass Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights or not heights[0]:
            return []

        # Step 1: Initialize sets and dimensions
        m, n = len(heights), len(heights[0])
        pacific = set()
        atlantic = set()

        # Step 2: DFS function
        def dfs(r, c, visited, prev_height):
            # Out of bounds or already visited or can't flow (height < prev)
            if (r < 0 or r >= m or c < 0 or c >= n or 
                (r, c) in visited or heights[r][c] < prev_height):
                return
            visited.add((r, c))
            # Explore all 4 directions
            for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
                dfs(r + dr, c + dc, visited, heights[r][c])

        # Step 3: Flood from Pacific (top and left)
        for c in range(n):
            dfs(0, c, pacific, -1)    # Top edge
        for r in range(m):
            dfs(r, 0, pacific, -1)    # Left edge

        # Step 4: Flood from Atlantic (bottom and right)
        for c in range(n):
            dfs(m-1, c, atlantic, -1) # Bottom edge
        for r in range(m):
            dfs(r, n-1, atlantic, -1) # Right edge

        # Step 5: Find intersection and convert to list
        result = list(pacific & atlantic)
        return [[r, c] for r, c in result]

• Line 4-5: Handle empty grid, return [].
• Line 8-10: Set up:
• m, n: Grid dimensions.
• pacific, atlantic: Sets for reachable cells.
• Line 13-20: DFS function:
• Line 15-17: Stop if out of bounds, visited, or height too low.
• Line 18: Mark current cell.
• Line 19-20: Recurse in 4 directions with current height.
• Line 23-26: Flood Pacific:
• Top (row 0), left (col 0), use -1 as prev_height (ocean).
• Line 29-32: Flood Atlantic:
• Bottom (row m-1), right (col n-1).
• Line 35-36: Get intersection, convert to list of [r, c].
• Time Complexity: O(mn)—each cell visited once per ocean.
• Space Complexity: O(mn)—sets store visited cells.

This is like flooding the map from the shores to find the meeting points!

Alternative Solution: BFS with Queues

Why an Alternative Approach?

The BFS with queues method uses breadth-first search to explore from the borders, queuing cells level-by-level. It’s O(mn) time and O(mn) space—more explicit but similar in performance. It’s like sending out waves from the oceans to see where they overlap!

How It Works

Picture it as waves spreading:

• Step 1: Queue border cells for Pacific and Atlantic.
• Step 2: BFS from each, mark reachable cells.
• Step 3: Find cells in both sets.

Step-by-Step Example

Example: heights = [[1,2],[3,4]]

• Pacific Queue: [(0,0), (0,1), (1,0)], BFS → {(0,0), (0,1), (1,0), (1,1)}.
• Atlantic Queue: [(0,1), (1,0), (1,1)], BFS → {(0,1), (1,0), (1,1)}.
• Overlap: {(0,1), (1,0), (1,1)}.
• Result: [[0,1], [1,0], [1,1]].

Code for BFS Approach

Copy codefrom 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])
        pacific = set()
        atlantic = set()

        def bfs(queue, visited):
            while queue:
                r, c = queue.popleft()
                visited.add((r, c))
                for dr, dc in [(-1,0), (1,0), (0,-1), (0,1)]:
                    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]):
                        queue.append((nr, nc))

        # Pacific borders
        pacific_q = deque()
        for c in range(n):
            pacific_q.append((0, c))
        for r in range(m):
            pacific_q.append((r, 0))
        bfs(pacific_q, pacific)

        # Atlantic borders
        atlantic_q = deque()
        for c in range(n):
            atlantic_q.append((m-1, c))
        for r in range(m):
            atlantic_q.append((r, n-1))
        bfs(atlantic_q, atlantic)

        return [[r, c] for r, c in pacific & atlantic]

• Time Complexity: O(mn)—each cell processed once.
• Space Complexity: O(mn)—queues and sets.

It’s a wave-spreading overlap finder!

Comparing the Two Solutions

• DFS from Borders (Best):
• Pros: O(mn), O(mn), recursive and clean.
• Cons: Stack depth.
• BFS with Queues (Alternative):
• Pros: O(mn), O(mn), explicit levels.
• Cons: Queue overhead.

DFS wins for elegance.

Additional Examples and Edge Cases

• [[1]]: [[0,0]].
• [[1,1],[1,1]]: All cells.
• [[2,1],[1,2]]: [[0,0], [1,1]].

DFS handles all.

Complexity Breakdown

• DFS: Time O(mn), Space O(mn).
• BFS: Time O(mn), Space O(mn).

DFS is sleek.

Key Takeaways

• DFS: Flood from edges!
• BFS: Wave it out!
• Flow: Paths converge.
• Python Tip: Sets rock—see [Python Basics](/python/basics).

Final Thoughts: Find That Flow

LeetCode 417: Pacific Atlantic Water Flow in Python is a water-tracing adventure. DFS from borders flows it fast, while BFS waves it wide. Want more grid fun? Try LeetCode 200: Number of Islands or LeetCode 695: Max Area of Island. Ready to trace? Head to Solve LeetCode 417 on LeetCode and find those flow spots today!