Skip to main content

417 - Pacific Atlantic Water Flow

Difficulty: Medium | Pattern: DFS / BFS (Multi-source) | Company tags: Amazon, Google, Facebook

Problem Statement​

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. The Atlantic Ocean touches the island's right and bottom edges.

Water can only flow in four directions to an adjacent cell if the adjacent cell's height is less than or equal to the current cell's height.

Find all cells where water can flow to both the Pacific and Atlantic oceans.

Return a 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:

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]]

Approach: Reverse BFS from Both Oceans — O(mn)​

Key insight: Instead of simulating water flow downhill, do BFS uphill starting from ocean borders. A cell can reach the Pacific iff it's reachable from the Pacific border going uphill. Same for Atlantic. Intersection = answer.

Algorithm Flow​

from collections import deque

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    m, n = len(heights), len(heights[0])
    
    def bfs(starts):
        visited = set(starts)
        queue = deque(starts)
        while queue:
            r, c = queue.popleft()
            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]):
                    visited.add((nr,nc))
                    queue.append((nr,nc))
        return visited
    
    pacific_starts = [(r,0) for r in range(m)] + [(0,c) for c in range(n)]
    atlantic_starts = [(r,n-1) for r in range(m)] + [(m-1,c) for c in range(n)]
    
    pac = bfs(pacific_starts)
    atl = bfs(atlantic_starts)
    
    return [[r,c] for r,c in pac & atl]

Dry Run (small grid)​

heights = [[1,2,2],[3,2,3],[2,4,5]]

Pacific BFS starts from row 0 and col 0, spreading uphill. Atlantic BFS starts from row 2 and col 2, spreading uphill. Intersection gives cells reachable by both.

Complexity​

  • Time: O(m × n) — each cell visited at most twice
  • Space: O(m × n)

Key Terms​

TermDefinition
Multi-source BFSBFS seeded from many starting cells simultaneously (here, an entire ocean border) instead of one node.
Reverse simulationFlowing "uphill" from the ocean toward the interior instead of simulating water flowing downhill from every cell.
Visited setSet of coordinates already reached by a given BFS, used to avoid revisiting and to answer "can reach ocean X" queries.
Set intersectionCells that appear in both the Pacific-reachable and Atlantic-reachable sets — the final answer.

FAQ​

Q: Why BFS from the oceans instead of from every cell? A: BFS from every cell independently would be O((mn)^2) in the worst case; seeding from the borders and flowing uphill visits each cell at most twice total, giving O(mn).

Q: Can DFS be used instead of BFS? A: Yes — the traversal order doesn't matter, only which cells are reachable, so recursive or iterative DFS with a visited set works identically.

Q: What if a cell can flow to only one ocean? A: It appears in only one of the two visited sets, so it's correctly excluded from the final intersection.

Q: How do we handle the corner cells (e.g., top-left)? A: They belong to both the Pacific's row-0/col-0 seed set, so they start in the Pacific BFS by definition; if they also flow to the Atlantic BFS's reachable region, they appear in the answer.

Q: What if the grid has only one row or one column? A: The border definitions still work — every cell is on some border, so seeding logic degrades gracefully without special-casing.

Quick Revision​

  • Goal: find cells that can drain to both the Pacific (top/left) and Atlantic (bottom/right).
  • Instead of simulating downhill flow from each cell, reverse the problem: BFS/DFS uphill from ocean borders.
  • A neighbor is reachable in the reverse search if neighbor height >= current height.
  • Run two independent multi-source searches: one from Pacific borders, one from Atlantic borders.
  • Answer = intersection of the two visited sets.
  • Time O(m×n), space O(m×n) for visited sets and queue.
  • Each cell is visited at most once per ocean, i.e., at most twice overall.
  • Edge cases: single row/column grids, uniform height grids (everything flows everywhere).