Find cells that can flow to both Pacific and Atlantic oceans.
This problem follows the Multi-source BFS/DFS pattern, commonly found in the Graphs category. Recognizing this pattern is key to solving it efficiently in an interview setting.
BFS from Pacific border and Atlantic border separately. Return intersection.
Reverse the flow: instead of flowing downhill from each cell, flow uphill from the ocean borders — this avoids O(m*n) DFS per cell.
pacific = set()
atlantic = set()
def dfs(r, c, visited, prevHeight):
if (r,c) in visited or r<0 or c<0 or r>=rows or c>=cols:
return
if heights[r][c] < prevHeight: return
visited.add((r,c))
for dr, dc in directions:
dfs(r+dr, c+dc, visited, heights[r][c])
# Start from borders
for c in range(cols):
dfs(0, c, pacific, 0)
dfs(rows-1, c, atlantic, 0)
for r in range(rows):
dfs(r, 0, pacific, 0)
dfs(r, cols-1, atlantic, 0)
return pacific & atlanticPractice Pacific Atlantic Water Flow and similar Graphs problems with flashcards. Build pattern recognition through active recall.
Practice this problem