Pacific Atlantic Water Flow

When we think of matrix problems in algorithm design, the Pacific Atlantic Water Flow stands out as a beautiful fusion of grid traversal, recursion, and search algorithms. In this article, we’ll solve understanding how water flows from elevation-based cells in a two-dimensional array toward both the Pacific and Atlantic Oceans using DFS and BFS, and how this problem answers several common search queries on Google.

What is the Pacific Atlantic Water Flow Problem?

You're given an m x n grid matrix of integers representing elevation levels. Water can only flow from a cell to another if the neighbor has equal or lower elevation. The Pacific touches the top and left borders of the matrix, and the Atlantic touches the bottom and right borders.

The goal is to find all grid cells from which water can flow to both oceans.

Why Does This Problem Matter?

This problem models real-world water flow and pathfinding. It’s essential in environmental simulations and geographic information systems (GIS). It also illustrates fundamental principles of reachability, making it an ideal practice for DFS and BFS.

How Does Water Flow from One Cell to Two Oceans?

To understand this, we simulate water flowing inward from the oceans using reverse traversal logic. Instead of starting from a cell and moving to the oceans, we flood the matrix from the Pacific and Atlantic borders and record which cells are visited.

Applying DFS for Ocean Reachability

We use two visited cells matrices: one for Pacific and one for Atlantic. Starting from the respective borders, we recursively mark reachable cells using Depth-First Search (DFS).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def pacificAtlantic(heights):
    if not heights: return []
    
    rows, cols = len(heights), len(heights[0])
    pacific = [[False]*cols for _ in range(rows)]
    atlantic = [[False]*cols for _ in range(rows)]

    def dfs(r, c, visited, prev_height):
        if (r < 0 or r >= rows or c < 0 or c >= cols or 
            visited[r][c] or heights[r][c] < prev_height):
            return
        visited[r][c] = True
        for dr, dc in [(0,1), (1,0), (0,-1), (-1,0)]:
            dfs(r + dr, c + dc, visited, heights[r][c])

    for i in range(rows):
        dfs(i, 0, pacific, heights[i][0])
        dfs(i, cols - 1, atlantic, heights[i][cols - 1])
    
    for j in range(cols):
        dfs(0, j, pacific, heights[0][j])
        dfs(rows - 1, j, atlantic, heights[rows - 1][j])

    result = []
    for i in range(rows):
        for j in range(cols):
            if pacific[i][j] and atlantic[i][j]:
                result.append([i, j])
    return result

BFS Alternative for Pathfinding

Breadth-First Search (BFS) can also be used to simulate matrix traversal layer by layer. It’s particularly effective when managing large grids to avoid recursion stack overflow.

Time and Space Complexity

• Time Complexity: O(m * n), where m and n are dimensions of the matrix, because we visit each cell at most twice.
• Space Complexity: O(m * n) for visited matrices and call stack or queue.

Common Questions People Ask

Here are the questions that usually ask on search engines:

How does water reach both the Pacific and Atlantic?

By tracking water flowing from the borders inward using DFS or BFS, we record all cells that can reach both oceans via non-decreasing elevation.

Why do we reverse the water flow direction?

Simulating water from each cell toward the borders would be computationally expensive. Instead, starting from the borders ensures efficient reachability tracking.

What algorithms can be used?

This problem is perfect for DFS, BFS, or a hybrid. It's a great example of grid search algorithms.

How does matrix traversal work here?

We iterate through border cells and explore neighboring elevations, marking visited cells in each direction.

Final Thoughts

The Pacific Atlantic Water Flow problem is more than a matrix exercise—it's a fantastic blend of recursion, pathfinding, and graph-style traversal on a two-dimensional array. Whether you're prepping for interviews or studying search algorithms, mastering this ensures you understand how to handle multiple constraints and grid reachability in elegant ways.