← Create New Paste

Pacific Atlantic Water Flow: Reverse the Search and the Problem Gets Easy

3 views
Pacific Atlantic Water Flow (LeetCode 417) gives you a grid of heights. The Pacific Ocean touches the top and left edges, the Atlantic touches the bottom and right edges. Rain can flow from a cell to a neighbor (up, down, left, right) if the neighbor's height is less than or equal to the current cell. Return every cell from which water can reach both oceans. The trap most candidates fall into The obvious idea is to start a DFS from every cell and check whether it can reach each ocean. That works, but it is O((m*n)^2) in the worst case because you repeat the same exploration from thousands of starting points. Interviewers usually let you say this out loud and then wait to see if you can improve it. The key insight: flow uphill from the oceans Instead of asking "can this cell reach the ocean?", ask "which cells can the ocean reach if water could climb?" Start from all cells on the Pacific border at once and move to a neighbor only if the neighbor is higher or equal. Every cell you visit can drain to the Pacific. Do the same from the Atlantic border. The answer is the intersection of the two visited sets. This is a multi-source search: you seed the stack or queue with every border cell of one ocean, not just one cell. Each cell is visited at most once per ocean, so the total cost is O(m*n) time and O(m*n) space. Sketch in Python def pacific_atlantic(h): if not h: return [] m, n = len(h), len(h[0]) def search(starts): seen = set(starts) stack = list(starts) while stack: r, c = stack.pop() for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r+dr, c+dc if 0 <= nr < m and 0 <= nc < n and (nr,nc) not in seen and h[nr][nc] >= h[r][c]: seen.add((nr,nc)); stack.append((nr,nc)) return seen pac = search([(0,c) for c in range(n)] + [(r,0) for r in range(m)]) atl = search([(m-1,c) for c in range(n)] + [(r,n-1) for r in range(m)]) return [list(p) for p in pac & atl] Details interviewers listen for - The comparison flips. Because you are walking backwards, the condition is neighbor >= current, not <=. Say why, because this is where bugs happen. - Corner cells belong to both border lists. Using a set for seeds avoids double work. - Iterative DFS or BFS avoids recursion depth issues on a 200x200 grid. Mention it even if you write recursion. - Edge cases: a single row or single column, where every cell touches both oceans; and a flat grid where everything is an answer. How to talk through it Start with the brute force, give its complexity, then explain the reversal in one sentence: "Rather than searching from 40,000 cells to the edges, I search from the edges inward twice." That framing shows the pattern transfers to other problems, such as Surrounded Regions or finding enclaves, where seeding from the border is also the trick. Practice saying it under pressure Knowing the reversal is one thing; explaining it calmly while a timer runs and an interviewer asks "why >= and not >?" is another. If you want support during the real thing, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, listening to the question and suggesting structured hints so you can stay on track with your own reasoning. Use it alongside honest practice: solve the problem twice from scratch, once with DFS and once with BFS, until the explanation feels natural.
Created Nov 17, 2026 15:29 Expires Nov 17, 2027 15:29