Pacific Atlantic Water Flow

Problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. Water can only flow to an adjacent cell with height less than or equal to the current cell's height. Given an m x n integer matrix heights, return a 2D list of grid coordinates where rain water can flow to both the Pacific and Atlantic oceans.

Examples

The brute-force approach

For each cell, DFS downward to check if it can reach the Pacific and separately if it can reach the Atlantic. Return cells that can reach both.

result = []
for each cell (r, c):
    if can_reach_pacific(r, c) and can_reach_atlantic(r, c):
        result.append([r, c])

O(m × n × (m+n)) — for each cell, DFS can visit the entire grid.

Spotting the pattern

This is a Graph Traversal problem. The key question to ask yourself:

Instead of flowing downhill from each cell to the ocean, can you "flow uphill" from the ocean to find all cells that drain into it? What changes in your movement rule?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.