LeetCode 417 - Pacific Atlantic Water Flow

The problem gives us a rectangular grid called heights, where each cell represents the elevation of a piece of land. Water can flow from one cell to another if the neighboring cell has a height less than or equal to the current cell.

leetcodemediumarraydepth-first-searchbreadth-first-searchmatrix

LeetCode Problem 417

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem gives us a rectangular grid called heights, where each cell represents the elevation of a piece of land. Water can flow from one cell to another if the neighboring cell has a height less than or equal to the current cell. Movement is allowed only in the four cardinal directions: up, down, left, and right.

The Pacific Ocean touches the top and left borders of the grid, while the Atlantic Ocean touches the bottom and right borders. A cell is considered valid if water starting from that cell can eventually reach both oceans through valid downhill or flat-height paths.

The key detail is the direction of water flow. Water moves from higher elevation to lower or equal elevation. At first glance, this suggests starting from every cell and simulating water flow outward. However, doing this independently for every cell would repeatedly explore the same regions and become inefficient.

The input is an m x n matrix where both dimensions can be as large as 200. That means there can be up to 40,000 cells total. Any solution worse than roughly linear or near-linear in the number of cells risks timing out.

The output should contain all coordinates [r, c] such that water from that position can flow to both oceans.

Several edge cases are important to recognize early:

  • A 1 x 1 grid trivially reaches both oceans because the single cell touches all borders.
  • Grids with all equal heights allow water to move freely in all directions.
  • Strictly increasing or decreasing grids create one-way flow constraints that can expose incorrect traversal logic.
  • Cells on ocean borders already have access to one ocean and may or may not reach the other.
  • Cycles can occur when neighboring cells have equal heights, so a visited structure is necessary.

Approaches

Brute Force Approach

The brute-force solution starts a DFS or BFS from every individual cell. For each starting position, we attempt to determine whether water can eventually reach the Pacific Ocean and whether it can eventually reach the Atlantic Ocean.

From a given cell, we recursively move to neighboring cells whose heights are less than or equal to the current cell, because water can only flow downhill or remain level. If we eventually touch a Pacific border, then the cell can reach the Pacific. Similarly, if we touch an Atlantic border, then the cell can reach the Atlantic.

This approach is correct because it directly simulates the exact movement rules described in the problem. However, it performs an enormous amount of repeated work. Neighboring cells often explore nearly identical paths repeatedly.

In the worst case, every DFS may traverse most of the grid. Since there are m * n starting cells, the total complexity becomes extremely large.

Optimal Approach

The key insight is to reverse the direction of the search.

Instead of asking:

"From this cell, can water flow to the ocean?"

we ask:

"Starting from the ocean, which cells can eventually flow into it?"

This reversal works because water flow is directional. If water can flow downhill from A to B, then during reverse traversal we can move from B to A whenever A >= B.

So rather than performing thousands of searches from interior cells, we perform only two traversals:

  • One traversal starting from all Pacific-border cells
  • One traversal starting from all Atlantic-border cells

During these traversals, we move only to neighboring cells with height greater than or equal to the current cell. That ensures reverse reachability corresponds exactly to forward water flow.

At the end:

  • pacific_reachable[r][c] tells us the cell can reach the Pacific
  • atlantic_reachable[r][c] tells us the cell can reach the Atlantic

Any cell reachable from both searches belongs in the answer.

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) DFS/BFS from every cell independently
Optimal O(m * n) O(m * n) Reverse traversal from ocean borders

Algorithm Walkthrough

  1. Create two visited sets, one for the Pacific Ocean and one for the Atlantic Ocean.

These sets record which cells can reach each ocean. We keep them separate because a cell may reach one ocean but not the other. 2. Identify all Pacific border cells.

The Pacific touches:

  • the top row
  • the left column

These cells are the starting points for the Pacific traversal because water can immediately flow into the Pacific from them. 3. Identify all Atlantic border cells.

The Atlantic touches:

  • the bottom row
  • the right column

These cells become the starting points for the Atlantic traversal. 4. Run DFS or BFS from all Pacific border cells.

During traversal, move only to neighboring cells whose height is greater than or equal to the current cell.

This reverse condition is critical. If the neighbor is higher or equal, then water could flow downhill from that neighbor into the current cell in the original problem direction. 5. Run DFS or BFS from all Atlantic border cells using the same rule.

After both traversals finish, each visited structure contains all cells capable of reaching that ocean. 6. Iterate through every cell in the grid.

If a cell exists in both visited sets, then water from that cell can reach both oceans. 7. Return all such coordinates.

Why it works

The algorithm relies on reverse reachability.

If water can flow from cell A to cell B in the original problem, then during reverse traversal we can move from B to A. By starting from ocean borders and exploring all reverse-valid paths, we discover every cell that could eventually drain into that ocean.

Since the Pacific and Atlantic traversals are independent, the intersection of their reachable sets contains exactly the cells that can flow to both oceans.

Python Solution

from typing import List, Set, Tuple

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        rows = len(heights)
        cols = len(heights[0])

        pacific_reachable: Set[Tuple[int, int]] = set()
        atlantic_reachable: Set[Tuple[int, int]] = set()

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(row: int, col: int, visited: Set[Tuple[int, int]]) -> None:
            visited.add((row, col))

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    0 <= new_row < rows
                    and 0 <= new_col < cols
                    and (new_row, new_col) not in visited
                    and heights[new_row][new_col] >= heights[row][col]
                ):
                    dfs(new_row, new_col, visited)

        # Pacific Ocean traversal
        for col in range(cols):
            dfs(0, col, pacific_reachable)

        for row in range(rows):
            dfs(row, 0, pacific_reachable)

        # Atlantic Ocean traversal
        for col in range(cols):
            dfs(rows - 1, col, atlantic_reachable)

        for row in range(rows):
            dfs(row, cols - 1, atlantic_reachable)

        result = []

        for row in range(rows):
            for col in range(cols):
                if (
                    (row, col) in pacific_reachable
                    and (row, col) in atlantic_reachable
                ):
                    result.append([row, col])

        return result

The implementation closely follows the reverse-flow strategy.

The dfs helper explores all cells reachable from a given ocean boundary. The visited set prevents infinite loops and duplicate work, especially in regions with equal heights.

The traversal condition:

heights[new_row][new_col] >= heights[row][col]

is the core insight of the solution. Since we are traversing backward from the ocean, we move toward equal or higher cells.

The algorithm performs four boundary traversals:

  • Top row for Pacific
  • Left column for Pacific
  • Bottom row for Atlantic
  • Right column for Atlantic

After both reachability maps are complete, we scan the entire grid and collect cells appearing in both sets.

Go Solution

package main

func pacificAtlantic(heights [][]int) [][]int {
	rows := len(heights)
	cols := len(heights[0])

	pacific := make([][]bool, rows)
	atlantic := make([][]bool, rows)

	for i := 0; i < rows; i++ {
		pacific[i] = make([]bool, cols)
		atlantic[i] = make([]bool, cols)
	}

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	var dfs func(int, int, [][]bool)

	dfs = func(row int, col int, visited [][]bool) {
		visited[row][col] = true

		for _, dir := range directions {
			newRow := row + dir[0]
			newCol := col + dir[1]

			if newRow < 0 || newRow >= rows ||
				newCol < 0 || newCol >= cols {
				continue
			}

			if visited[newRow][newCol] {
				continue
			}

			if heights[newRow][newCol] < heights[row][col] {
				continue
			}

			dfs(newRow, newCol, visited)
		}
	}

	// Pacific traversal
	for col := 0; col < cols; col++ {
		dfs(0, col, pacific)
	}

	for row := 0; row < rows; row++ {
		dfs(row, 0, pacific)
	}

	// Atlantic traversal
	for col := 0; col < cols; col++ {
		dfs(rows-1, col, atlantic)
	}

	for row := 0; row < rows; row++ {
		dfs(row, cols-1, atlantic)
	}

	result := [][]int{}

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if pacific[row][col] && atlantic[row][col] {
				result = append(result, []int{row, col})
			}
		}
	}

	return result
}

The Go implementation uses [][]bool instead of hash sets for visited tracking. This is efficient because grid dimensions are known in advance.

Go slices are dynamically sized, so the result is built incrementally using append.

Unlike Python, Go does not have nested function recursion with implicit closure behavior by default, so the DFS function is declared as a variable before assignment.

There are no integer overflow concerns because the problem constraints are small relative to Go's integer capacity.

Worked Examples

Example 1

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

Pacific Traversal

Initial Pacific boundary cells:

Source Coordinates
Top row (0,0) (0,1) (0,2) (0,3) (0,4)
Left column (0,0) (1,0) (2,0) (3,0) (4,0)

Starting from (0,0):

Current Cell Height Reachable Higher/Equal Neighbors
(0,0) 1 (1,0), (0,1)
(0,1) 2 (1,1), (0,2)
(1,1) 2 (2,1), (1,2)
(2,1) 4 (3,1), (2,2)

Eventually the Pacific traversal marks all cells capable of draining into the Pacific.

Atlantic Traversal

Initial Atlantic boundary cells:

Source Coordinates
Bottom row (4,0) (4,1) (4,2) (4,3) (4,4)
Right column (0,4) (1,4) (2,4) (3,4) (4,4)

Starting from (4,4):

Current Cell Height Reachable Higher/Equal Neighbors
(4,4) 4 (3,4)
(3,4) 5 none
(4,3) 2 (3,3), (4,4)
(3,3) 4 none

After both traversals complete:

Cell Pacific Reachable Atlantic Reachable Included
(0,4) Yes Yes Yes
(1,3) Yes Yes Yes
(1,4) Yes Yes Yes
(2,2) Yes Yes Yes
(3,0) Yes Yes Yes
(3,1) Yes Yes Yes
(4,0) Yes Yes Yes

Final output:

[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

Example 2

heights = [[1]]

The single cell lies on:

  • top border
  • bottom border
  • left border
  • right border

So it belongs to both oceans immediately.

Cell Pacific Atlantic
(0,0) Yes Yes

Output:

[[0,0]]

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is visited at most once per ocean traversal
Space O(m * n) Visited structures store up to all cells

The important observation is that although DFS is launched from many border cells, each cell is processed only once for the Pacific traversal and once for the Atlantic traversal. Therefore the total work scales linearly with the number of cells in the matrix.

The recursion stack in the worst case may also reach O(m * n) depth if the grid forms a long increasing path.

Test Cases

from typing import List

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        rows = len(heights)
        cols = len(heights[0])

        pacific = set()
        atlantic = set()

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        def dfs(r, c, visited):
            visited.add((r, c))

            for dr, dc in directions:
                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]
                ):
                    dfs(nr, nc, visited)

        for c in range(cols):
            dfs(0, c, pacific)
            dfs(rows - 1, c, atlantic)

        for r in range(rows):
            dfs(r, 0, pacific)
            dfs(r, cols - 1, atlantic)

        return sorted([
            [r, c]
            for r in range(rows)
            for c in range(cols)
            if (r, c) in pacific and (r, c) in atlantic
        ])

solution = Solution()

# Example 1 from problem statement
assert sorted(solution.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]
])) == sorted([
    [0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]
])

# Single cell grid
assert solution.pacificAtlantic([[1]]) == [[0,0]]

# All equal heights, every cell reaches both oceans
assert sorted(solution.pacificAtlantic([
    [1,1],
    [1,1]
])) == sorted([
    [0,0],[0,1],[1,0],[1,1]
])

# Strictly increasing rows and columns
assert sorted(solution.pacificAtlantic([
    [1,2],
    [3,4]
])) == sorted([
    [0,1],[1,0],[1,1]
])

# Single row grid
assert sorted(solution.pacificAtlantic([
    [1,2,3,4]
])) == sorted([
    [0,0],[0,1],[0,2],[0,3]
])

# Single column grid
assert sorted(solution.pacificAtlantic([
    [1],
    [2],
    [3]
])) == sorted([
    [0,0],[1,0],[2,0]
])

# Basin in the center
assert sorted(solution.pacificAtlantic([
    [5,5,5],
    [5,1,5],
    [5,5,5]
])) == sorted([
    [0,0],[0,1],[0,2],
    [1,0],[1,2],
    [2,0],[2,1],[2,2]
])

# Large flat region
assert sorted(solution.pacificAtlantic([
    [10,10,10],
    [10,10,10],
    [10,10,10]
])) == sorted([
    [0,0],[0,1],[0,2],
    [1,0],[1,1],[1,2],
    [2,0],[2,1],[2,2]
])
Test Why
Example 1 Validates the standard mixed-height scenario
Single cell Tests smallest possible input
All equal heights Ensures equal-height traversal works correctly
Increasing grid Validates directional reachability
Single row Tests degenerate horizontal case
Single column Tests degenerate vertical case
Basin in center Ensures low interior cells cannot incorrectly escape
Large flat region Tests extensive equal-height connectivity

Edge Cases

A single-cell grid is the smallest valid input and can easily expose incorrect border handling. Since the lone cell touches every edge simultaneously, it belongs to both oceans. The implementation handles this naturally because the same cell is included in both DFS traversals.

Grids where all heights are equal are another important edge case. In such matrices, water can move freely between all neighboring cells. An implementation that incorrectly uses a strict greater-than comparison instead of greater-than-or-equal would fail here. The solution correctly allows traversal when heights are equal.

Interior basins are also tricky. Consider a low cell surrounded by taller cells. Water from that basin cannot escape outward because movement is only allowed downhill or level. Reverse traversal handles this perfectly because DFS from the oceans cannot climb down into the basin if the surrounding cells are taller.

Long monotonic paths can create deep recursion chains. For example, a snake-like increasing path through the matrix may cause DFS depth to approach the total number of cells. The algorithm still remains correct because every cell is visited only once per ocean, though in Python iterative BFS could be used if recursion depth becomes a concern in practice.