Which cells drain to both oceans? Flip the flow: flood uphill from each coastline, then keep the cells both tides reach.
▼The problem
An m × n grid of heights is an island. The Pacific touches its top and left edges, the Atlantic its bottom and right edges. Water flows from a cell to any neighbour of equal or lower height (and off the grid into the ocean from an edge cell). Return every cell whose water can reach **both** oceans.
Example (the LeetCode one):
[[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]]TRY IT ON LEETCODE ▶
The solution
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
pac, atl = set(), set()
def climb(r, c, seen): # flood uphill
seen.add((r, c))
for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)):
if (0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in seen
and heights[nr][nc] >= heights[r][c]):
climb(nr, nc, seen)
for r in range(rows):
climb(r, 0, pac); climb(r, cols - 1, atl)
for c in range(cols):
climb(0, c, pac); climb(rows - 1, c, atl)
return [[r, c] for r, c in pac & atl]Transcript
Pacific Atlantic Water Flow. An island is a grid of heights. The Pacific touches its top and left edges; the Atlantic, its bottom and right.
Rain flows to any neighbor that is equal or lower. Drop rain on this five: it runs down to the Pacific, and down to the Atlantic too. Which cells reach both oceans? Here, seven of them.
The obvious way: start at every cell and follow the water downhill. But each search can cover the whole island, twenty-five cells, up to twenty-five steps each. That's m times n, squared.
Flip it. Instead of water running down to the sea, let the sea climb up. Start at the Pacific's edge and flood uphill, into any neighbor that is equal or higher. Every cell the tide reaches can drain to the Pacific. Do the same from the Atlantic. The answer is where the tides overlap.
In code, a helper adds a cell to a seen set, then climbs to every unseen neighbor at least as high. Call it from every edge cell of each ocean, then return the cells in both sets.
Let's run it. The Pacific starts on its nine edge cells and climbs inland. It holds sixteen cells. The Atlantic climbs from the bottom and right. It also holds sixteen. Seven cells are wet from both sides: the answer.
Each tide visits a cell at most once, so the time is m times n, and the seen sets take m times n space.
Don't chase the water down. Let the oceans climb up. That's Pacific Atlantic Water Flow.