Pacific Atlantic Water Flow
Given a height grid where water flows to equal-or-lower neighbors, find every cell that can drain to both the Pacific (top/left) and Atlantic (bottom/right) oceans.
- m == heights.length
- n == heights[r].length
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10⁵
Intuition
Pacific Atlantic water flow finds cells from which water can reach both oceans, where water flows only to a neighbour of equal or lower height. The Pacific borders the top and left edges, the Atlantic the bottom and right. The direct approach — starting from each cell and searching downhill to see which oceans it reaches — is O((mn)²) in the worst case, because every cell launches its own traversal over a potentially large region. The fix is to reverse the direction of the search: - Start at the ocean borders and move to neighbours of equal or greater height, marking every cell that could flow back down. Water flowing downhill from a cell to the ocean is the same relation as climbing uphill from the ocean to that cell. Running one traversal from all Pacific border cells marks every cell that drains to the Pacific; a second from the Atlantic borders does the same. The answer is the intersection of the two sets. That turns quadratic work into two linear passes, because each cell is visited at most once per ocean. The comparison flips with the direction — moving outward from the ocean, a neighbour is valid when its height is greater than or equal to the current cell's. Keeping the downhill comparison while searching upward is the standard error and produces a nearly empty result. Seed the traversal with every border cell, not just the corners, and allow equal heights so that flat plateaus connected to a border are correctly included.
Search upward from each ocean instead of downward from each cell. Reversing the flow condition to >= means one traversal per ocean marks everything that can drain into it, and the answer is the intersection of the two marked sets.
Approach
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(R*C) time and O(R*C) space.
See why the direct search is slow
Searching downhill from every cell costs O((mn)^2) in the worst case, since each of the mn cells can traverse a large region. The structure of the problem allows far better.
Reverse the flow direction
Water reaching the ocean from a cell is the same relation as climbing from the ocean to that cell. Searching outward from the borders replaces mn traversals with two.
Seed from all border cells
Enqueue the entire top and left edges for the Pacific, and the entire bottom and right edges for the Atlantic. Seeding only the corners misses most of the reachable area.
Flip the height comparison
Moving outward, a neighbour is valid when its height is greater than or equal to the current cell's. Keeping the downhill comparison while searching upward is the standard error and yields a nearly empty answer.
Allow equal heights
Using strict > breaks flat regions, since water crosses a plateau freely. Equality must be permitted or connected level areas are wrongly excluded.
Intersect the two visited sets
A cell reachable in both traversals drains to both oceans. Scan the grid once and collect every coordinate marked in both — that intersection is the answer.
Cost of the two traversals
Each cell is visited at most once per ocean, giving O(m · n) time and O(m · n) space for the two visited grids and the traversal stack.
Solution & live demo
Common pitfalls
Simulating downhill flow from every cell
for each cell: dfs downhill, check if it reaches both oceans
pacVis = bfs(pacific_border) atlVis = bfs(atlantic_border)
That's a separate search per cell — O((RC)²). Two searches from the borders answer the question for every cell at once, because reachability is symmetric under the reversed comparison.
Using > instead of >= when climbing
if heights[nr][nc] > heights[r][c]:
if heights[nr][nc] >= heights[r][c]:
Water flows to cells of equal or lower height, so climbing backwards must accept equal heights too. The strict version blocks every plateau and misses large regions.
Sharing one visited array between the two searches
vis = [[False]*C for _ in range(R)] # reused
def bfs(starts):
vis = [[False]*C for _ in range(R)]The two oceans' reachable sets overlap — that overlap is the answer. Sharing the array lets the first search block the second, and the intersection collapses to nothing.
Edge cases
The single cell touches both borders at once, so it always drains to both oceans.
Every cell reaches every border since >= holds everywhere; the whole grid qualifies.
They sit on both a Pacific and an Atlantic border edge simultaneously and are trivially in both sets.
Uphill walk from both borders can still reach it if there's a nondecreasing path; if not, it's excluded from one or both sets.