~25 minutes · Day 55 · reverse flood fill · Python
Tonight's problem is Pacific Atlantic Water Flow. It is a classic interview trap because the obvious direction feels natural: start at every cell and ask where the water can drain. That works on tiny grids, then collapses when the interviewer expects you to notice the question is easier backwards.
Instead of asking where each cell drains, flood inward from each ocean and intersect the two reachable sets.
The grid cells are the graph nodes. Two cells have an edge if they are up, down, left, or right neighbors. Water can flow from a cell to a neighbor with height less than or equal to it. A plain graph traversal can follow those edges.
Brute force is: for every cell, run a downhill search and see whether that one search touches the Pacific border and the Atlantic border. If the grid is R * C cells, one search can touch R * C cells, and you might do that from every cell: O((R*C)^2) time.
Reverse the question. Instead of starting from a high cell and flowing down, start from an ocean edge and walk inward to cells that could have flowed down into you. That means the comparison flips: from the ocean side, you may move only to an equal-or-higher neighbor.
Python's set is the right memory structure here: one set for cells that can reach the Pacific, one set for cells that can reach the Atlantic, then a set intersection for cells that can reach both.
def flood(starts):
seen, stack = set(starts), list(starts) # cells reaching one ocean
while stack:
r, c = stack.pop()
for nr, nc in neighbors(r, c): # in-bounds four-neighbors
if (nr, nc) in seen: continue
if heights[nr][nc] < heights[r][c]: continue
seen.add((nr, nc)); stack.append((nr, nc)) # climb inward
return seen
pacific = flood(pacific_border) # top row + left col
atlantic = flood(atlantic_border) # bottom row + right col
answer = list(pacific & atlantic) # both oceans
In the real submission, neighbors just yields the four in-bounds neighbors, and the two border lists are built from the outer rows and columns. The invariant is doing the heavy lifting: two floods, then intersect.
Numbers are heights. Each flood climbs inward from its own border to equal-or-higher cells; the three dotted cells lie in both reachable sets, so they drain to both oceans.
New problem: a city grid has two emergency exits, one along the north-west border and one along the south-east border. A signal can travel from a high tower to an equal-or-lower neighboring tower. Which towers can reach both exits?
Before opening the reveal, predict the direction: do you start from every tower, or from the exits?
Start from the exits. From each exit border, flood inward only to equal-or-higher towers, then intersect the two reachable sets. Same invariant, different story.
| Approach | Time | Space |
|---|---|---|
| Brute force: search downhill from every cell | O((R*C)^2) | O(R*C) |
| Reverse flooding: search inward from both oceans | O(R*C) | O(R*C) |
The improvement comes from visiting each cell at most once per ocean, instead of rediscovering the same downhill regions from many different starting cells.
1. Which direction makes Pacific Atlantic efficient?
2. During a reverse flood, which neighbor may you enter?
3. Spot the bug in this reverse flood condition:
if heights[nr][nc] <= heights[r][c]:
seen.add((nr, nc))4. After both ocean floods, what is returned?
Solve Pacific Atlantic Water Flow in your Notion tracker using the cycle: predict → attempt → compare → encode.
Watch NeetCode — Pacific Atlantic Water Flow after your attempt, as the compare step. Focus on the moment he flips the search direction.