Pacific Atlantic Water Flow

Difficulty: Medium Source: NeetCode

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.

Water can only flow in four directions: up, down, left, right. Water flows from a cell to an adjacent one only if the adjacent cell’s height is less than or equal to the current cell.

Given an m x n integer matrix heights where heights[r][c] represents the height of cell (r, c), return a list of grid coordinates where water can flow 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]]

Constraints:

• m == heights.length, n == heights[i].length
• 1 <= m, n <= 200
• 0 <= heights[i][j] <= 10^5

Prerequisites

Before attempting this problem, you should be comfortable with:

• DFS / BFS on grids — visiting neighbors under a condition
• Multi-source traversal — starting from border cells rather than interior cells
• Set intersection — finding cells reachable from both oceans

1. Brute Force (DFS from each cell)

Intuition

For each cell, run two DFS searches: one to check if water can flow to the Pacific, and one to check if it can reach the Atlantic. A cell reaches the Pacific if it can reach the top or left border; Atlantic if it can reach the bottom or right border. Add the cell to results if both are reachable.

Algorithm

1. For each cell (r, c), run DFS flowing downhill (next cell height ≤ current height).
2. Check if Pacific border or Atlantic border is reachable.
3. Collect cells where both are reachable.

Solution

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    rows, cols = len(heights), len(heights[0])

    def can_reach(r, c, ocean):
        visited = set()
        def dfs(r, c):
            if (r, c) in visited:
                return False
            visited.add((r, c))
            # Check if we've reached the target ocean border
            if ocean == 'P' and (r == 0 or c == 0):
                return True
            if ocean == 'A' and (r == rows - 1 or c == cols - 1):
                return True
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and heights[nr][nc] <= heights[r][c]:
                    if dfs(nr, nc):
                        return True
            return False
        return dfs(r, c)

    result = []
    for r in range(rows):
        for c in range(cols):
            if can_reach(r, c, 'P') and can_reach(r, c, 'A'):
                result.append([r, c])
    return result


print(pacificAtlantic([[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]]))
# [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Complexity

• Time: O(M² * N²) — one DFS per cell per ocean
• Space: O(M * N) for visited sets

2. Reverse BFS/DFS from Ocean Borders

Intuition

Instead of checking each cell’s reachability, reverse the direction: start from the ocean borders and traverse uphill (next cell height ≥ current height). All cells reachable from Pacific borders going uphill can flow to the Pacific. Same for Atlantic. The answer is their intersection.

This avoids redundant work by sharing traversal across all cells — each cell is visited at most twice total (once per ocean traversal).

Algorithm

1. Initialize Pacific reachable set with all top-row and left-column cells.
2. Initialize Atlantic reachable set with all bottom-row and right-column cells.
3. Run BFS (or DFS) from each set, expanding to neighbors with height ≥ current.
4. Return the intersection of both sets.

Solution

from collections import deque

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    rows, cols = 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 < rows and 0 <= nc < cols 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 = [(0, c) for c in range(cols)] + [(r, 0) for r in range(1, rows)]
    atlantic_starts = [(rows-1, c) for c in range(cols)] + [(r, cols-1) for r in range(rows-1)]

    pacific = bfs(pacific_starts)
    atlantic = bfs(atlantic_starts)

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


print(sorted(pacificAtlantic([[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]])))
# [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

print(pacificAtlantic([[1]]))  # [[0,0]]

Complexity

• Time: O(M * N) — each cell visited at most twice
• Space: O(M * N) for the visited sets and queue

Common Pitfalls

Going downhill vs uphill. In the forward direction (from cell to ocean), water flows downhill (to cells with equal or lower height). In the reverse direction (from ocean borders inward), we traverse uphill (to cells with equal or higher height). Make sure you use >= in the reverse BFS.

Including corner cells in both ocean starts. The top-left corner touches the Pacific and the bottom-right corner touches the Atlantic. Don’t double-count cells when building pacific_starts and atlantic_starts — use range(1, rows) for one of the directions to avoid duplicates (though duplicates don’t affect correctness, just efficiency).

Result ordering. The problem doesn’t require sorted output, but checking your result against expected output is easier if you sort both.