Pacific Atlantic Water Flow
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Water flows from a cell to a neighbour of equal or lower height. List the cells from which water can reach BOTH the Pacific (top and left edges) and the Atlantic (bottom and right edges).
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If water flows downhill from a cell to the ocean, the same path read backwards goes uphill from the ocean.
- Hint 2Run two floods from the borders and keep the cells that both reached.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Imagine the tide rising. Water floods in from the Pacific coast and creeps uphill: it can enter a neighbouring cell only if that cell is as high or higher. Mark everything the Pacific tide reaches. Do the same from the Atlantic. The cells wet by both tides are the answer, because rain falling there could run down to either ocean.
- The obvious way
From every cell search downhill for both oceans: O((rows x columns)²).
- The key insight
Flood once from all Pacific border cells and once from all Atlantic border cells, each time moving to a neighbour whose height is greater than or equal to the current one. Collect the cells in both marked sets. Two floods, each visiting every cell once.
- The algorithm
- Start cells: top row and left column for the Pacific; bottom row and right column for the Atlantic.
- Flood from the Pacific cells to neighbours of equal or greater height.
- Do the same for the Atlantic.
- Return the cells marked by both.
Watch it run
Exampleheights rows: 1 3 2 / 4 5 1 / 2 1 1
The Pacific tide starts on the top row and left column and climbs: it reaches 6 cells, but not the 1s in the right column and bottom row.
Pacific wets 6 cells
Where people slip
- The reverse flow moves to heights >= current (uphill), the opposite of the forward rule.
- Corner cells belong to both starting borders; that is fine.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def pacific_atlantic(heights):
rows, columns = len(heights), len(heights[0])
def tide(starts): # every cell this ocean's tide can reach
wet = set(starts)
to_visit = list(starts)
while to_visit:
r, c = to_visit.pop()
for next_row, next_column in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if (0 <= next_row < rows and 0 <= next_column < columns
and (next_row, next_column) not in wet
and heights[next_row][next_column] >= heights[r][c]): # climbing uphill
wet.add((next_row, next_column))
to_visit.append((next_row, next_column))
return wet
pacific = tide([(0, column) for column in range(columns)] + [(row, 0) for row in range(rows)])
atlantic = tide([(rows - 1, column) for column in range(columns)] + [(row, columns - 1) for row in range(rows)])
return [[row, column] for (row, column) in pacific & atlantic]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.