Intuition
- I had previously attempted this by observing that “up and left” would always lead to the Pacific ocean and “down and right” would always lead to the Atlantic ocean. What I failed to consider was the case where water flowed “up, left, up, right, up, left, left, …” until it reached the pacific ocean, like a game of snake.
- What I ended up doing was to Use the usual DFS, but mark whether I reached the Pacific or Atlantic oceans, respectively, then return those indices that ended up reaching both.
Code
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
pacific_q = deque()
for c in range(n):
pacific_q.append((0, c))
for r in range(m):
pacific_q.append((r, 0))
atlantic_q = deque()
for c in range(n):
atlantic_q.append((m - 1, c))
for r in range(m):
atlantic_q.append((r, n - 1))
def adj(r, c):
return [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)] # left, right, up, down
def inbound(r, c):
return 0 <= r < m and 0 <= c < n
def bfs(q):
visited = set(q)
while q:
r, c = q.popleft()
for i, j in adj(r, c):
if inbound(i, j) and (i, j) not in visited and heights[i][j] >= heights[r][c]:
visited.add((i, j))
q.append((i, j))
return visited
return [list(x) for x in bfs(pacific_q) & bfs(atlantic_q)]Notes
Cards
START Basic Front: Pacific Atlantic Water Flow Back: Use multi source BFS (pacific ocean and atlantic ocean in queue) and expand outward. END