Hints — p24 Pacific Atlantic Water Flow

Read one at a time.

Hint 1 — Spot the trap. “For each cell, BFS to see if it reaches both oceans” is O((MN)²) and times out on big grids. More importantly, the interview signal is whether you pivot away from this; the right answer is fundamentally a different algorithm.

Hint 2 — Invert the question. Instead of “from each cell, can I reach the ocean?”, ask “from the ocean, which cells can be reached?” Same answer, dramatically smaller work: O(MN) instead of O((MN)²).

Hint 3 — Flip the comparison. Going forward (cell → ocean), water moves to neighbors with lower or equal height. Going backward (ocean → cell), you move to neighbors with higher or equal height. This sign flip is the #1 bug source — write it as a comment in the code.

Hint 4 — Multi-source BFS, not K separate BFSes. The Pacific isn’t one cell; it’s an entire border. Seed your BFS queue with ALL Pacific border cells UP FRONT, mark each visited, then run a single BFS. Same for Atlantic. Two BFS runs total, each O(MN). Don’t BFS from each border cell separately.

Hint 5 — Combine. After the two BFS runs you have two bool matrices: pac[r][c] and atl[r][c]. The answer is every (r, c) where both are true. One pass to collect.

If still stuck: look at pacific_atlantic_bfs in solution.py — the inverted BFS is the entire trick.