Pacific Atlantic Water Flow

Difficulty: Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix
Link: https://leetcode.com/problems/pacific-atlantic-water-flow/

Problem Description

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: The following cells can flow to the Pacific and Atlantic oceans, as shown below:
[0,4]: [0,4] -> Pacific Ocean 
       [0,4] -> Atlantic Ocean
[1,3]: [1,3] -> [0,3] -> Pacific Ocean 
       [1,3] -> [1,4] -> Atlantic Ocean
[1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean 
       [1,4] -> Atlantic Ocean
[2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean 
       [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean
[3,0]: [3,0] -> Pacific Ocean 
       [3,0] -> [4,0] -> Atlantic Ocean
[3,1]: [3,1] -> [3,0] -> Pacific Ocean 
       [3,1] -> [4,1] -> Atlantic Ocean
[4,0]: [4,0] -> Pacific Ocean 
       [4,0] -> Atlantic Ocean
Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2:


Input: heights = [[1]]
Output: [[0,0]]
Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints:

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105

Solution

1. Problem Deconstruction

Technical Restatement
Given an m x n matrix heights representing land elevations, determine all cells (ri, ci) from which water can flow to both the Pacific Ocean (touching the top/left edges) and Atlantic Ocean (touching the bottom/right edges). Water flows to adjacent cells (north, south, east, west) with height ≤ current cell.

Beginner Explanation
Imagine a grid where each cell has a height. Rainwater can flow from a cell to its neighboring cells (up, down, left, right) if the neighbor is at the same height or lower. Cells on the top/left borders can send water to the Pacific, and cells on the bottom/right borders can send water to the Atlantic. Find all cells where water can reach both oceans.

Mathematical Formulation
Let H[r][c] be the height at cell (r, c). Define:

P = Set of cells with a path (c₁ → c₂ → ... → cₖ) where c₁ is on Pacific border, H[cᵢ] ≥ H[cᵢ₊₁] for all i.
A = Analogous set for Atlantic.
Return P ∩ A.

Constraint Analysis

Grid size (m, n ≤ 200):
- Limits solutions to ≤ O(mn) time. Brute-force O(m²n²) is invalid.
- Edge case: Full grid traversal required.
Heights up to 1e5:
- No impact on algorithms but requires handling large integers.
Single-cell grid (m = n = 1):
- Directly included in both oceans.

2. Intuition Scaffolding

Analogies

Real-World: Imagine two flood zones (Pacific/Atlantic) spreading inland, following uphill paths. Cells submerged by both floods are the answer.
Gaming Analogy: In a strategy game, two armies (Pacific/Atlantic) conquer territories by moving uphill. Territories captured by both armies are strategic points.
Math Analogy: Compute reachability sets from two sources (ocean borders) under a monotonicity constraint (height non-decreasing).

Common Pitfalls

Direction of Flow: Starting from inner cells and checking paths to oceans (O(m²n²)).
Single BFS Pass: Attempting to track both oceans in one traversal.
Overlooking Equal Heights: Missing cells with equal heights in BFS/DFS.
Edge Initialization: Incorrectly initializing only corners instead of entire borders.
Space Inefficiency: Storing paths instead of boolean reachability.

3. Approach Encyclopedia

Optimal Approach (Reverse BFS)
Idea: Compute reachability from ocean borders via BFS, moving to higher/equal cells. Intersect Pacific and Atlantic reachability sets.

Pseudocode:

Initialize pacific_reach and atlantic_reach as m x n boolean grids.  
For Pacific:  
    Add all top-row and left-column cells to a queue.  
    BFS to all cells ≥ current height, marking pacific_reach.  
For Atlantic:  
    Add all bottom-row and right-column cells to a queue.  
    BFS similarly, marking atlantic_reach.  
Collect cells where both flags are True.

Complexity Proof

Time: O(2mn + mn) = O(mn). Each BFS visits each cell once.
Space: O(2mn) for reachability matrices.

Visualization

Pacific BFS:           Atlantic BFS:  
T T T T T             . . . . A  
T → → → .             . → → A A  
T → . . .             . → A . .  
T . . . .             A A . . .  
T . . . .             A . . . .  
Intersection: Cells marked in both grids.

4. Code Deep Dive

Optimal Solution Code

def pacificAtlantic(heights):
    if not heights:
        return []
    
    m, n = len(heights), len(heights[0])
    dirs = [(-1,0), (1,0), (0,-1), (0,1)]
    pacific = [[False]*n for _ in range(m)]
    atlantic = [[False]*n for _ in range(m)]
    from collections import deque
    
    # Pacific BFS
    q = deque()
    for i in range(m):
        pacific[i][0] = True
        q.append((i, 0))
    for j in range(1, n):
        pacific[0][j] = True
        q.append((0, j))
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                if not pacific[nr][nc] and heights[nr][nc] >= heights[r][c]:
                    pacific[nr][nc] = True
                    q.append((nr, nc))
    
    # Atlantic BFS
    q = deque()
    for i in range(m):
        atlantic[i][n-1] = True
        q.append((i, n-1))
    for j in range(n-1):
        atlantic[m-1][j] = True
        q.append((m-1, j))
    while q:
        r, c = q.popleft()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                if not atlantic[nr][nc] and heights[nr][nc] >= heights[r][c]:
                    atlantic[nr][nc] = True
                    q.append((nr, nc))
    
    # Collect results
    return [[r, c] for r in range(m) for c in range(n) if pacific[r][c] and atlantic[r][c]]

Line-by-Line Insights

Lines 6-8: Initialize Pacific BFS with left and top borders.
Lines 13-15: BFS expands to higher/equal neighbors, marking reachability.
Lines 19-21: Atlantic BFS starts from right and bottom.
Lines 29-30: Collect cells common to both reachability sets.

Edge Case Handling

Single Cell (Line 2): Returns [[0,0]] immediately.
Grid with Uniform Heights: All cells are in the result.

5. Complexity War Room

Hardware Considerations

At m = n = 200, each reachability matrix uses 200x200 = 40,000 bits (~10KB). Fits in CPU cache.

Approach Comparison

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(m²n²)	O(1)	5/10	❌ Fails large N
Reverse BFS	O(mn)	O(mn)	8/10	✅ Optimal & Clear

6. Pro Mode Extras

Variants

LC 417 (This Problem): Solved via reverse BFS.
LC 407 (Trapping Rain Water II): Uses priority queue to track boundaries.
LC 778 (Swim in Rising Water): Binary search + DFS.

Interview Cheat Sheet

Key Insight: Reverse traversal from ocean borders.
Mention First: “This can be optimized to O(mn) via BFS from both oceans.”
Test Case Tips: Check single-cell, uniform grid, and disconnected regions.

#417 - Pacific Atlantic Water Flow