Checking, for every cell, “can water flow downhill from here all the way to the Pacific, and separately all the way to the Atlantic” means a traversal per cell — expensive. The trick is to reverse the question: instead of asking “where can I flow to?”, flood fill backwards from each ocean’s border, walking to neighbors that are higher or equal (since water flows from high to low, walking backwards up a valid flow path means non-decreasing height). Whatever a backward flood fill from the Pacific border reaches is exactly the set of cells that can flow to the Pacific, and likewise for the Atlantic; the answer is the intersection of those two reachable sets.
(GridVisualizer only renders binary 0/1 land-and-water grids, and heights here has many distinct values, so this problem owns a small folder-local visualizer — see the optimal solution’s trace — that can render the full heights grid, both labeled coastlines, and the two reverse floods overlapping cell by cell.)
Flood Fill From Every Cell
Time O(m·n · (m+n))Space O(m·n)For each cell, run its own flood fill following the actual downhill rule (move to a neighbor with height <= current) and check whether that flood fill ever touches the Pacific-adjacent border or the Atlantic-adjacent border.
class Solution: def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]: rows, cols = len(heights), len(heights[0])
def can_reach(sr, sc, is_target_border): visited = {(sr, sc)} stack = [(sr, sc)] while stack: r, c = stack.pop() if is_target_border(r, c): return True for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): nr, nc = r + dr, c + dc if ( 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and heights[nr][nc] <= heights[r][c] ): visited.add((nr, nc)) stack.append((nr, nc)) return False
result = [] for r in range(rows): for c in range(cols): reaches_pacific = can_reach(r, c, lambda rr, cc: rr == 0 or cc == 0) reaches_atlantic = can_reach( r, c, lambda rr, cc: rr == rows - 1 or cc == cols - 1 ) if reaches_pacific and reaches_atlantic: result.append([r, c]) return resultWhy it’s correct: it directly checks the definition — a downhill (or flat) path exists from the cell to each ocean’s border. Complexity: each of the O(m·n) cells can trigger a flood fill visiting up to O(m·n) cells → O((m·n)²) time in the worst case, with O(m·n) space for the visited set of one flood fill at a time. Massively redundant, since nearby cells’ flood fills overlap almost entirely.
Reverse Flood Fill From Both Coastlines
OptimalTime O(m·n)Space O(m·n)Run the flood fill only twice total, not once per cell — once from every cell touching the Pacific (top row + left column), once from every cell touching the Atlantic (bottom row + right column) — but walk uphill (to a neighbor with height >= current), since that is the reverse of a valid downhill flow. A cell reached by the Pacific flood fill can flow to the Pacific; a cell reached by the Atlantic flood fill can flow to the Atlantic. Intersect the two reachable sets.
class Solution: def pacificAtlantic(self, heights: list[list[int]]) -> list[list[int]]: if not heights or not heights[0]: return [] rows, cols = len(heights), len(heights[0]) pacific, atlantic = set(), set()
def dfs(r, c, visited, prev_height): if ( r < 0 or r >= rows or c < 0 or c >= cols or (r, c) in visited or heights[r][c] < prev_height ): return visited.add((r, c)) for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)): dfs(r + dr, c + dc, visited, heights[r][c])
for c in range(cols): dfs(0, c, pacific, heights[0][c]) dfs(rows - 1, c, atlantic, heights[rows - 1][c]) for r in range(rows): dfs(r, 0, pacific, heights[r][0]) dfs(r, cols - 1, atlantic, heights[r][cols - 1])
return [list(cell) for cell in pacific & atlantic]Trace data lives in this folder’s data.ts and replays the reverse flood fill from both coastlines on the example grid [[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-indexed rows/cols).
Watch the two coast floods march toward each other: sky and indigo spread only to cells of equal or greater height, and a cell turns emerald with a star the instant it holds both colors — that star is the answer condition.
The grid to trace: a 5 by 5 island, heights 1 to 7. The Pacific touches the top and left edges, the Atlantic the bottom and right edges. Instead of asking every cell where its water flows, the reverse flood fill asks each coastline what it can reach: water flows downhill to an ocean, so the reverse flood simply walks to neighbors of equal or greater height. A cell reached by BOTH floods is the answer.
Intersecting the two reachable sets gives {(0,4), (1,3), (1,4), (2,2), (3,0), (3,1), (4,0)}, matching the expected output [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].
Why it’s correct: a cell can flow downhill to the Pacific if and only if there is a non-increasing path from it to the Pacific border — equivalently, a non-decreasing path from the Pacific border to it, which is exactly what the reverse flood fill discovers. The same logic applies to the Atlantic. A cell satisfies the problem’s condition exactly when it’s in both reachable sets. Complexity: each ocean’s flood fill visits every cell at most once → O(m·n) time total for both floods, O(m·n) space for the two visited sets.