Pacific Atlantic Water Flow (LeetCode 417)
An m x n rectangular island sits between two oceans: the Pacific along its top and left edges, and the Atlantic along its bottom and right edges. You're given the island's height map, an m x n matrix heights where heights[r][c] is the elevation of cell (r, c).
Rain falling on any cell flows to a north/south/east/west neighbor only if that neighbor's height is no greater than the current cell's, and water reaches an ocean as soon as it flows off the cell bordering it.
Return the list of coordinates [r, c] from which rain can reach both oceans.
Worked Examples
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]][[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]](1,3) steps up to (0,3) for the Pacific and sideways to (1,4) for the Atlantic, and (2,2) reaches the Pacific via (1,2)→(0,2) and the Atlantic via (2,3)→(2,4). Other cells only drain to one ocean, or (like the peak at (1,4) height 4) sit high enough to reach both directly. Several of these cells have more than one valid downhill route; only one needs to exist.heights = [[1]][[0,0]]⚖️Formal Constraints & Bounds
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105
Core Insight
Reversing the flow direction transforms an expensive all-pairs problem into two linear graph traversals.
Real-World Scenario & Production Applications
Topographical watershed modeling, hydrological drainage divide analysis.
Step-by-Step Execution Trace Table
| Cell | Height | Pacific Reached? | Atlantic Reached? | Both? |
|---|---|---|---|---|
| (0, 4) | 5 | Yes (top coast) | Yes (right coast) | YES |
| (1, 3) | 4 | Yes (via (0,3)) | Yes (via (1,4)) | YES |
| (2, 2) | 5 | Yes (via (1,2)) | Yes (via (2,3)) | YES |
| (0, 0) | 1 | Yes (Pacific corner) | No (Atlantic blocked) | No |
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]][[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]| Cell | Height | Pacific Reached? | Atlantic Reached? | Both? |
|---|---|---|---|---|
| (0, 4) | 5 | Yes (top coast) | Yes (right coast) | YES |
| (1, 3) | 4 | Yes (via (0,3)) | Yes (via (1,4)) | YES |
| (2, 2) | 5 | Yes (via (1,2)) | Yes (via (2,3)) | YES |
| (0, 0) | 1 | Yes (Pacific corner) | No (Atlantic blocked) | No |
| 1 | pacific = set() |
| 2 | atlantic = set() |
| 3 | def dfs(r, c, vis): |
| 4 | vis.add((r, c)) |
| 5 | for each neighbor (nr, nc) inside the grid: |
| 6 | if (nr, nc) not in vis and heights[nr][nc] >= heights[r][c]: |
| 7 | dfs(nr, nc, vis) |
| 8 | dfs from all 4 boundaries into respective ocean sets |
| 9 | return intersection of pacific and atlantic |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Simulating water flow forward from every cell to the ocean takes time. The inversion trick is to reverse the flow: start from the ocean boundaries and search uphill (). By performing two reverse traversals (one from the Pacific, one from the Atlantic), the target cells are simply the intersection of cells reachable by both ocean tides in time.
🔄 The Analogy: Instead of Asking Where Rain Goes, Ask Where the Tide Reaches
Rather than dropping a raindrop on every cell and simulating where it flows, stand at the ocean's edge and ask a different question: "if I let water climb uphill from here, which inland cells could it reach?" Water naturally flows from high ground to low or equal ground, so reversing that — climbing from an ocean cell to any neighbor at an equal or greater height — retraces every path that could have flowed down into that ocean cell in the forward direction. Do this once from every Pacific-adjacent cell, and once from every Atlantic-adjacent cell; anywhere both reverse-searches reach is a cell whose water can reach both oceans.
🔑 The Key Idea in the Code
This turns an O((M·N)²) "simulate every cell's downhill journey" problem into two O(M·N) reverse floods plus a set intersection — a massive complexity win purely from asking the question backward.
Forward simulation from every cell TLE: Starting independent BFS/DFS searches from each interior cell to see if water reaches both oceans. The reverse perspective is required: start multi-source traversals from the Pacific border inward, and Atlantic border inward, flowing strictly uphill (
neighbor_height >= curr_height).Uphill flow inversion error: When traversing backward from oceans into the continent, water flows from lower heights to equal-or-higher heights. Writing
neighbor_height <= curr_heightinverts the logic and finds ocean-bound paths instead of uphill sources.Combining visited sets with bitmasks incorrectly: Using a single visited set instead of two independent sets
pacific_reachableandatlantic_reachable. The answer is the set intersectionpacific_reachable & atlantic_reachable.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Grid drainage / flow reachability to multiple opposing boundaries.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: reverse flow travels uphill (heights[neighbor] >= heights[curr]).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Simulating flow downhill from every cell: O((R·C)²) vs optimal O(R · C).
Shared visited state: Pacific and Atlantic traversals must use separate visited sets.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I perform reverse DFS from all 4 boundaries into
pacificandatlanticsets. In reverse flow, water moves uphill (neighbor_h >= curr_h). After both ocean traversals complete, the answer is the intersection of both sets. Runs in O(R · C) time and O(R · C) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: Reverses flow direction: runs DFS/BFS from Pacific ocean boundaries (top/left) and Atlantic ocean boundaries (bottom/right) moving uphill (height >= prev_height). Finds intersection of visited matrices.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(M · N) Recursion stack depth. Two boolean visited matrices (pacific, atlantic) of size M x N.
T(M, N) = 2 · O(M · N) = O(M · N)
Derivation Progression
2M + 2N boundary origins
Seeds searches from ocean shorelines.
if H[nr][nc] ≥ H[r][c]
Water flows downhill, so search climbs uphill from ocean inward.
pacific[r][c] ∧ atlantic[r][c]
Finds mutual reachability in O(M · N) pass.
Variable Definitions
Total number of rows in the elevation grid
Total number of columns in the elevation grid
Memory Architecture & Bounds
O(M · N) Recursion stack depth
O(M · N) Two boolean visited matrices
O(M · N) Coordinate list
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "water flows to both Pacific and Atlantic", "rain water flows downhill". Simulating downward flow from each interior cell takes ( ops, TLE). A Senior SWE inverts the search: Reverse Boundary Flow climbing UPWARD from the Oceans in strictly time!
. Time budget: linear.
Reversed elevation check: when walking from ocean inward, water "climbs" uphill: the neighbor height must be current cell height!
Pacific Atlantic Water Flow (LeetCode 417)
An m x n rectangular island sits between two oceans: the Pacific along its top and left edges, and the Atlantic along its bottom and right edges. You're given the island's height map, an m x n matrix heights where heights[r][c] is the elevation of cell (r, c).
Rain falling on any cell flows to a north/south/east/west neighbor only if that neighbor's height is no greater than the current cell's, and water reaches an ocean as soon as it flows off the cell bordering it.
Return the list of coordinates [r, c] from which rain can reach both oceans.
Worked Examples
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]][[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]](1,3) steps up to (0,3) for the Pacific and sideways to (1,4) for the Atlantic, and (2,2) reaches the Pacific via (1,2)→(0,2) and the Atlantic via (2,3)→(2,4). Other cells only drain to one ocean, or (like the peak at (1,4) height 4) sit high enough to reach both directly. Several of these cells have more than one valid downhill route; only one needs to exist.heights = [[1]][[0,0]]⚖️Formal Constraints & Bounds
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105
Core Insight
Reversing the flow direction transforms an expensive all-pairs problem into two linear graph traversals.
Real-World Scenario & Production Applications
Topographical watershed modeling, hydrological drainage divide analysis.
Step-by-Step Execution Trace Table
| Cell | Height | Pacific Reached? | Atlantic Reached? | Both? |
|---|---|---|---|---|
| (0, 4) | 5 | Yes (top coast) | Yes (right coast) | YES |
| (1, 3) | 4 | Yes (via (0,3)) | Yes (via (1,4)) | YES |
| (2, 2) | 5 | Yes (via (1,2)) | Yes (via (2,3)) | YES |
| (0, 0) | 1 | Yes (Pacific corner) | No (Atlantic blocked) | No |
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]][[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]| Cell | Height | Pacific Reached? | Atlantic Reached? | Both? |
|---|---|---|---|---|
| (0, 4) | 5 | Yes (top coast) | Yes (right coast) | YES |
| (1, 3) | 4 | Yes (via (0,3)) | Yes (via (1,4)) | YES |
| (2, 2) | 5 | Yes (via (1,2)) | Yes (via (2,3)) | YES |
| (0, 0) | 1 | Yes (Pacific corner) | No (Atlantic blocked) | No |
| 1 | pacific = set() |
| 2 | atlantic = set() |
| 3 | def dfs(r, c, vis): |
| 4 | vis.add((r, c)) |
| 5 | for each neighbor (nr, nc) inside the grid: |
| 6 | if (nr, nc) not in vis and heights[nr][nc] >= heights[r][c]: |
| 7 | dfs(nr, nc, vis) |
| 8 | dfs from all 4 boundaries into respective ocean sets |
| 9 | return intersection of pacific and atlantic |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Simulating water flow forward from every cell to the ocean takes time. The inversion trick is to reverse the flow: start from the ocean boundaries and search uphill (). By performing two reverse traversals (one from the Pacific, one from the Atlantic), the target cells are simply the intersection of cells reachable by both ocean tides in time.
🔄 The Analogy: Instead of Asking Where Rain Goes, Ask Where the Tide Reaches
Rather than dropping a raindrop on every cell and simulating where it flows, stand at the ocean's edge and ask a different question: "if I let water climb uphill from here, which inland cells could it reach?" Water naturally flows from high ground to low or equal ground, so reversing that — climbing from an ocean cell to any neighbor at an equal or greater height — retraces every path that could have flowed down into that ocean cell in the forward direction. Do this once from every Pacific-adjacent cell, and once from every Atlantic-adjacent cell; anywhere both reverse-searches reach is a cell whose water can reach both oceans.
🔑 The Key Idea in the Code
This turns an O((M·N)²) "simulate every cell's downhill journey" problem into two O(M·N) reverse floods plus a set intersection — a massive complexity win purely from asking the question backward.
Forward simulation from every cell TLE: Starting independent BFS/DFS searches from each interior cell to see if water reaches both oceans. The reverse perspective is required: start multi-source traversals from the Pacific border inward, and Atlantic border inward, flowing strictly uphill (
neighbor_height >= curr_height).Uphill flow inversion error: When traversing backward from oceans into the continent, water flows from lower heights to equal-or-higher heights. Writing
neighbor_height <= curr_heightinverts the logic and finds ocean-bound paths instead of uphill sources.Combining visited sets with bitmasks incorrectly: Using a single visited set instead of two independent sets
pacific_reachableandatlantic_reachable. The answer is the set intersectionpacific_reachable & atlantic_reachable.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Grid drainage / flow reachability to multiple opposing boundaries.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: reverse flow travels uphill (heights[neighbor] >= heights[curr]).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Simulating flow downhill from every cell: O((R·C)²) vs optimal O(R · C).
Shared visited state: Pacific and Atlantic traversals must use separate visited sets.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I perform reverse DFS from all 4 boundaries into
pacificandatlanticsets. In reverse flow, water moves uphill (neighbor_h >= curr_h). After both ocean traversals complete, the answer is the intersection of both sets. Runs in O(R · C) time and O(R · C) space."
Complexity & Mathematical Proof
O(M · N)
Look at the execution steps: Reverses flow direction: runs DFS/BFS from Pacific ocean boundaries (top/left) and Atlantic ocean boundaries (bottom/right) moving uphill (height >= prev_height). Finds intersection of visited matrices.
O(M · N) Auxiliary
Look at memory allocations: Call stack uses O(M · N) Recursion stack depth. Two boolean visited matrices (pacific, atlantic) of size M x N.
T(M, N) = 2 · O(M · N) = O(M · N)
Derivation Progression
2M + 2N boundary origins
Seeds searches from ocean shorelines.
if H[nr][nc] ≥ H[r][c]
Water flows downhill, so search climbs uphill from ocean inward.
pacific[r][c] ∧ atlantic[r][c]
Finds mutual reachability in O(M · N) pass.
Variable Definitions
Total number of rows in the elevation grid
Total number of columns in the elevation grid
Memory Architecture & Bounds
O(M · N) Recursion stack depth
O(M · N) Two boolean visited matrices
O(M · N) Coordinate list
Boundary Best / Worst Cases
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "water flows to both Pacific and Atlantic", "rain water flows downhill". Simulating downward flow from each interior cell takes ( ops, TLE). A Senior SWE inverts the search: Reverse Boundary Flow climbing UPWARD from the Oceans in strictly time!
. Time budget: linear.
Reversed elevation check: when walking from ocean inward, water "climbs" uphill: the neighbor height must be current cell height!