LeetCode 417: Pacific Atlantic Water Flow

Problem Restatement

We are given an m x n matrix heights.

Each cell represents land height.

Water can flow from one cell to another adjacent cell if the next cell has height less than or equal to the current cell.

Adjacent means four directions only:

up, down, left, right

The Pacific Ocean touches the top and left edges.

The Atlantic Ocean touches the bottom and right edges.

Return all coordinates [r, c] where water can flow to both oceans.

The constraints are 1 <= m, n <= 200 and 0 <= heights[r][c] <= 10^5. The source examples include heights = [[1]], whose output is [[0,0]].

Input and Output

Item	Meaning
Input	Matrix `heights`
Output	List of coordinates `[r, c]`
Pacific border	Top row and left column
Atlantic border	Bottom row and right column
Flow rule	Water flows to equal or lower height
Movement	Four directions only

Example function shape:

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    ...

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

One valid output is:

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

For example, cell [2, 2] has height 5.

It can flow toward the Pacific through a path that reaches the top or left edge.

It can also flow toward the Atlantic through a path that reaches the bottom or right edge.

Example 2:

heights = [[1]]

The answer is:

[[0, 0]]

The only cell touches both oceans.

First Thought: Search From Every Cell

A direct approach is to start a DFS or BFS from every cell.

For each cell, simulate water flowing downhill or flat:

next_height <= current_height

If the search reaches the Pacific border and the Atlantic border, include the cell.

This is correct, but it repeats too much work.

A grid can have up to:

200 * 200 = 40000

cells.

Starting a traversal from every cell can become expensive.

Key Insight

Reverse the direction.

Instead of asking:

Can this cell flow to the ocean?

ask:

Which cells can reach this ocean if we walk backward?

Original water flow goes from high to low:

neighbor_height <= current_height

Reverse traversal goes from low to high:

neighbor_height >= current_height

Start from all Pacific-border cells and walk uphill or flat. Every cell reached this way can flow down to the Pacific.

Do the same from all Atlantic-border cells.

The answer is the intersection of both reachable sets.

Algorithm

Create two boolean matrices:

Matrix	Meaning
`pacific`	Cell can flow to the Pacific
`atlantic`	Cell can flow to the Atlantic

Run DFS from all Pacific-border cells:

top row
left column

Run DFS from all Atlantic-border cells:

bottom row
right column

In reverse DFS, from cell (r, c), move to neighbor (nr, nc) only if:

heights[nr][nc] >= heights[r][c]

After both traversals, collect every cell where:

pacific[r][c] and atlantic[r][c]

Correctness

A cell can flow to the Pacific if there exists a path from that cell to a Pacific border where heights never increase along the water-flow direction.

If we reverse that path, it starts from the Pacific border and moves through heights that never decrease.

That is exactly what the reverse DFS allows:

next_height >= current_height

So every cell marked by the Pacific reverse traversal can flow to the Pacific.

The same reasoning applies to the Atlantic traversal.

A cell can flow to both oceans exactly when it appears in both reachable sets.

The algorithm returns precisely those cells.

Therefore, the returned coordinate list is correct.

Complexity

Metric	Value	Why
Time	`O(mn)`	Each cell is visited at most once per ocean
Space	`O(mn)`	Two visited matrices and recursion stack

Here m is the number of rows and n is the number of columns.

Implementation

from typing import List

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

        pacific = [[False] * n for _ in range(m)]
        atlantic = [[False] * n for _ in range(m)]

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

        def dfs(r: int, c: int, visited: list[list[bool]]) -> None:
            visited[r][c] = True

            for dr, dc in directions:
                nr = r + dr
                nc = c + dc

                if nr < 0 or nr >= m or nc < 0 or nc >= n:
                    continue

                if visited[nr][nc]:
                    continue

                if heights[nr][nc] < heights[r][c]:
                    continue

                dfs(nr, nc, visited)

        for r in range(m):
            dfs(r, 0, pacific)
            dfs(r, n - 1, atlantic)

        for c in range(n):
            dfs(0, c, pacific)
            dfs(m - 1, c, atlantic)

        answer = []

        for r in range(m):
            for c in range(n):
                if pacific[r][c] and atlantic[r][c]:
                    answer.append([r, c])

        return answer

Code Explanation

We create two visited matrices:

pacific = [[False] * n for _ in range(m)]
atlantic = [[False] * n for _ in range(m)]

A True value means the cell can reach that ocean.

The DFS marks cells by reverse flow:

def dfs(r: int, c: int, visited: list[list[bool]]) -> None:

When visiting a cell, we mark it:

visited[r][c] = True

Then we inspect its four neighbors.

A neighbor outside the grid is ignored.

A neighbor already visited is ignored.

A neighbor lower than the current cell is ignored:

if heights[nr][nc] < heights[r][c]:
    continue

This condition enforces reverse flow. We can only move to equal or higher cells.

Then we start DFS from the ocean borders.

Pacific:

dfs(r, 0, pacific)
dfs(0, c, pacific)

Atlantic:

dfs(r, n - 1, atlantic)
dfs(m - 1, c, atlantic)

Finally, we collect cells reachable from both:

if pacific[r][c] and atlantic[r][c]:
    answer.append([r, c])

Iterative BFS Version

The same idea can be written with BFS to avoid recursion depth concerns.

from collections import deque
from typing import List

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

        def bfs(starts: list[tuple[int, int]]) -> list[list[bool]]:
            visited = [[False] * n for _ in range(m)]
            queue = deque()

            for r, c in starts:
                if not visited[r][c]:
                    visited[r][c] = True
                    queue.append((r, c))

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

            while queue:
                r, c = queue.popleft()

                for dr, dc in directions:
                    nr = r + dr
                    nc = c + dc

                    if nr < 0 or nr >= m or nc < 0 or nc >= n:
                        continue

                    if visited[nr][nc]:
                        continue

                    if heights[nr][nc] < heights[r][c]:
                        continue

                    visited[nr][nc] = True
                    queue.append((nr, nc))

            return visited

        pacific_starts = []
        atlantic_starts = []

        for r in range(m):
            pacific_starts.append((r, 0))
            atlantic_starts.append((r, n - 1))

        for c in range(n):
            pacific_starts.append((0, c))
            atlantic_starts.append((m - 1, c))

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

        return [
            [r, c]
            for r in range(m)
            for c in range(n)
            if pacific[r][c] and atlantic[r][c]
        ]

Testing

def normalize(items):
    return sorted(map(tuple, items))

def test_pacific_atlantic():
    s = Solution()

    result1 = s.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],
    ])

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

    assert normalize(result1) == normalize(expected1)

    assert s.pacificAtlantic([[1]]) == [[0, 0]]

    result3 = s.pacificAtlantic([
        [1, 2],
        [4, 3],
    ])

    assert normalize(result3) == normalize([[0, 1], [1, 0], [1, 1]])

    result4 = s.pacificAtlantic([
        [1, 1],
        [1, 1],
    ])

    assert normalize(result4) == normalize([[0, 0], [0, 1], [1, 0], [1, 1]])

    print("all tests passed")

Test Notes

Test	Why
Standard matrix	Checks normal multi-path behavior
`[[1]]`	Single cell touches both oceans
`2 x 2` matrix	Checks small border-heavy grid
All equal heights	Every cell can flow to both oceans