LeetEye LeetEye
Medium Graph Traversal ~5 min

Pacific Atlantic Water Flow

graphs pacific-atlantic-water-flow

Problem

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.

Examples

Example 1
Input: nums = [1,2,3]
Output: result
Key Insight

Reverse the flow: start from oceans and flow "uphill."

Reverse the flow: DFS 'uphill' from Pacific edges, DFS 'uphill' from Atlantic edges. Answer = intersection of both reachable sets.

How to Approach This Problem

Pattern Recognition: When you see keywords like pacific atlantic water flow graphs, think Graph Traversal.

Step-by-Step Reasoning

1 Water flows from cell A to B if:
Answer: A's height >= B's height (water flows downhill or flat)
Water flows to equal or lower heights.
2 Searching "uphill" from ocean means:
Answer: Move to cells with >= height
Reverse of downhill. If water can flow from B to A, we can reach B from A when going uphill.
3 Starting from oceans is better because:
Answer: Fewer starting points (only edges)
Edge cells are O(m+n), vs O(mn) interior cells. Two DFS from edges, then intersect.
4 Pacific-adjacent cells are:
Answer: Top row and left column
Pacific touches top and left edges.
5 A cell is in the answer if:
Answer: Reachable from both
Must be able to flow to BOTH oceans.
6 We run DFS:
Answer: Once from Pacific edges, once from Atlantic edges
Track reachability separately, then find intersection.

Solution

def pacificAtlantic(heights: List[List[int]]) -> List[List[int]]:
    rows, cols = len(heights), len(heights[0])
    pacific, atlantic = set(), set()
    
    def dfs(r, c, visit, prev_height):
        if (r < 0 or r >= rows or c < 0 or c >= cols or
            (r, c) in visit or heights[r][c] < prev_height):
            return
        
        visit.add((r, c))
        dfs(r + 1, c, visit, heights[r][c])
        dfs(r - 1, c, visit, heights[r][c])
        dfs(r, c + 1, visit, heights[r][c])
        dfs(r, c - 1, visit, heights[r][c])
    
    for c in range(cols):
        dfs(0, c, pacific, 0)        # Top row (Pacific)
        dfs(rows - 1, c, atlantic, 0) # Bottom row (Atlantic)
    
    for r in range(rows):
        dfs(r, 0, pacific, 0)        # Left col (Pacific)
        dfs(r, cols - 1, atlantic, 0) # Right col (Atlantic)
    
    return list(pacific & atlantic)

Complexity Analysis

Time O(m × n)
Space O(m × n)

Master This Pattern

Build intuition with interactive MCQs. Practice Graph Traversal problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye