417. Pacific Atlantic Water Flow

Pacific Atlantic Water Flow is a common interview-style matrix question frequently asked by MAANG companies (Meta, Microsoft, Google, Amazon, etc.). This is because it tests whether you can spot overlapping work and convert a “check every cell” idea into a boundary-based traversal. It’s exactly the kind of problem where one key observation separates a slow solution from an elegant one.

Problem statement

You are given an m x n integer matrix, heights, representing the height above sea level of each cell in the matrix. The entire matrix represents an island where it rains more than usual.

The island is surrounded by ocean water on its borders:

• The Pacific Ocean is on the top and left borders of the grid.
• The Atlantic Ocean is on the bottom and right borders of the grid.

Rain water can flow from a cell to any of its four neighboring cells (up, down, left, right) if and only if the neighboring cell’s height is less than or equal to the current cell’s height (water flows from higher/equal to lower/equal).

Return a 2D list of matrix coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200
• 0 <= heights[r][c] <= 10⁵

Examples

1 / 5

Naive approach: Start DFS from every cell

One of the initial thoughts is to run a DFS from every cell and check whether water can reach both oceans. From a starting cell (r, c), we explore neighbors only when the height does not increase, because water can only flow from a cell to a neighbor with height less than or equal to the current height. While exploring, we keep two flags:

• One becomes true if we touch the top or left border (Pacific).
• The other becomes true if we touch the bottom or right border (Atlantic).

If both flags become true, we include that cell in the answer.

As we repeat this for each cell, many searches end up walking through the same regions of the grid again and again. For example, if a large flat area exists, DFS from dozens of nearby cells will traverse almost identical paths. This makes the approach very slow on bigger inputs. In the worst case it can take O((m × n)²) time because we may do a near-complete traversal from each of the m × n cells. The space cost is also non-trivial because each search needs a visited structure (or recursion/queue space), which can grow up to O(m × n).

Key observation

Instead of starting a fresh DFS from every cell, we can flip the problem around and compute reachability from the oceans inward. Normally, water flows from a cell to a neighbor that is lower or equal. If we reverse this, we can start from an ocean border and move inward only to neighbors that are higher or equal. This reversed move is valid because if a neighbor is higher (or equal), then water from that neighbor could have flowed down (or flat) into our current cell, and eventually to the ocean.

Any cell that is reachable from both of these reverse searches is exactly a cell from which water can flow to both oceans in the original direction.

Optimzed solution using Depth First Search (DFS)

We solve this problem using two depth-first searches, one for each ocean.

DFS for Pacific side:
We begin from the cells along the top edge and the left edge, because those borders touch the Pacific Ocean. From these border cells, we explore inward, but we only step into neighboring cells that are high enough for water to be able to flow back down toward the border. As the search runs, we mark every cell as visited, meaning water from that cell can eventually reach the Pacific.

DFS for Atlantic side:
We repeat the exact same idea starting from the cells along the bottom edge and the right edge, because those borders touch the Atlantic Ocean. Again, we explore inward only through valid moves, and we mark every cell as visited

After both searches finish, we scan the grid and collect the cells that were marked reachable in both searches. Those cells are exactly the ones from which rain water can flow to both the Pacific and Atlantic oceans.

Step-by-step algorithm

1. Compute and store the matrix size as m = len(heights) and n = len(heights[0]). Next, create two m x n boolean matrixes initialized with False:
   1. pac to mark cells that can reach the Pacific.
   2. atl to mark cells that can reach the Atlantic.
2. Run DFS for the Pacific ocean by using all Pacific-border cells as starting points:
   1. For every column, c, in range(n), call dfs(0, c, pac) to start from the top row.
   2. For every row, r, in range(m), call dfs(r, 0, pac) to start from the left column.
   3. After this step, pac[r][c] == True means cell (r, c) can reach the Pacific in the forward direction.
3. Run DFS for the Atlantic ocean by using all Atlantic-border cells as starting points:
   1. For every c in range(n), call dfs(m - 1, c, atl) to start from the bottom row.
   2. For every r in range(m), call dfs(r, n - 1, atl) to start from the right column.
   3. After this step, atl[r][c] == True means cell (r, c) can reach the Atlantic in the forward direction.
4. After finishing both DFS, return all cells that are marked True in both reachability grids, as those cells can drain into both oceans.

The helper function, dfs(r, c, visited), works as follows:

1. Marks the current cell, visited[r][c], as True.
2. Tries moving in the four directions:
   1. (1,0): Right
   2. (-1,0): Left
   3. (0,1): Down
   4. (0,-1): Up
3. For each neighbor (nr, nc), it continues DFS only if:
   1. The neighbor is inside the matrix.
   2. It has not been visited yet (False).
   3. heights[nr][nc] >= heights[r][c] (this is the reverse-flow condition).

The slides below help to understand the solution better.

1 / 11

Python code for the optimal solution

The following Python code implements the optimal approach by running two DFS traversals from the ocean borders.

def pacificAtlantic(heights):
    m, n = len(heights), len(heights[0])

    # pac[r][c] = reachable from Pacific, atl[r][c] = reachable from Atlantic
    pac = [[False] * n for _ in range(m)]
    atl = [[False] * n for _ in range(m)]

    def dfs(r, c, visited):
        # Mark this cell as reachable from the current ocean
        visited[r][c] = True

        # Try all 4 neighbors
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc

            # Valid cell + not visited yet
            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc]:
                # Reverse-flow rule:
                # From the ocean we can move to neighbors that are higher/equal,
                # meaning water could flow back down to the ocean in the original direction.
                if heights[nr][nc] >= heights[r][c]:
                    dfs(nr, nc, visited)

    # Run DFS from all Pacific-border cells (top row and left column)
    for c in range(n):
        dfs(0, c, pac)
    for r in range(m):
        dfs(r, 0, pac)

    # Run DFS from all Atlantic-border cells (bottom row and right column)
    for c in range(n):
        dfs(m - 1, c, atl)
    for r in range(m):
        dfs(r, n - 1, atl)

    # Cells reachable from both are the answer
    return [[r, c] for r in range(m) for c in range(n) if pac[r][c] and atl[r][c]]


# Driver code (no expected outputs)
def main():
    test_cases = [
        [[1]],

        [[5, 1, 4, 4, 2]],

        [[5, 5, 5],
         [5, 1, 5],
         [5, 5, 5]],

        [[1, 2, 3, 4],
         [2, 3, 4, 5],
         [3, 4, 5, 6]],

        [[9, 8, 7, 6],
         [8, 7, 6, 5],
         [7, 6, 5, 4]],
    ]

    for idx, heights in enumerate(test_cases, 1):
        result = pacificAtlantic(heights)

        # Sort for stable printing (problem allows any order)
        result_sorted = sorted(result)

        print(f"{idx}.\theights =\n\t" + "\n\t".join(str(row) for row in heights))
        print(f"\n\tOutput: {result_sorted}")
        print("-" * 75)


if __name__ == "__main__":
    main()

Time complexity

The time complexity of this solution is O(m x n) because each cell in the grid is visited at most once during the Pacific DFS and at most once during the Atlantic DFS, and each visit inspects up to four neighbors, which is constant work.

Space complexity 

The space complexity of this solution is O(m x n) because it stores two m x n boolean matrixes (pac and atl) to record reachability, and the DFS recursion stack can also grow to O(m x n) in the worst case when the traversal forms a long path.

Common mistakes to avoid

Here are some common mistakes to avoid, along with useful interview tips.

• Incorrect height comparison: When climbing inland from the ocean, you must move to a neighbor only if its height is greater than or equal to the current cell.
• Boundary mix-up: Ensure the Pacific is mapped to the top/left edges and the Atlantic to the bottom/right; swapping these will lead to incorrect reachability sets.
• Forgetting the visited check: You must track visited cells immediately to avoid infinite recursion loops when the matrix contains plateaus (multiple cells of the same height).
• Neglecting empty or edge cases: Always validate the input; an empty matrix or a single-row/single-column matrix can cause index errors if not handled early.