Solutions
- For each grid (i, j), do BFS twice for both Pacific and Atlantic flow: O(n^4)
- For each grid (i, j), do BFS twice, but this time, can stop on grids already visited: slightly better
- For each grid (i, j) on each coastline, do BFS and return the grids that visited from both: O(n^3)
Algorithm
- Initialize m ⅹ n matrix flow_p, flow_a <- False.
- For each coastline (i, j) of Pacific Ocean, do BFS:
- flow_p[i][j] <- True
- for each neighbor (ni, nj):
- visit only if flow_p[ni][nj] == False.
- visit only if heights[i][j] <= heights[ni][nj].
- For each coastline (i, j) of Atlantic, do BFS (same but flow_a)
- Return the grids (i, j) such that both flow_p[i][j] and flow_a[i][j] are True.
Python Code
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m, n = len(heights), len(heights[0])
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]
reachable_p = [[False for j in range(n)] for i in range(m)]
reachable_a = [[False for j in range(n)] for i in range(m)]
def bfs(r, c, reachable):
queue = [(r, c)]
while queue:
r, c = queue.pop(0)
for i in range(4):
x, y = r+dx[i], c+dy[i]
if (-1<x<m and -1<y<n and
not reachable[x][y] and
heights[r][c] <= heights[x][y]):
reachable[x][y] = True
queue.append((x, y))
for i in range(m):
if not reachable_p[i][0]:
reachable_p[i][0] = True
bfs(i, 0, reachable_p)
for j in range(1, n):
if not reachable_p[0][j]:
reachable_p[0][j] = True
bfs(0, j, reachable_p)
for i in range(m):
if not reachable_a[i][n-1]:
reachable_a[i][n-1] = True
bfs(i, n-1, reachable_a)
for j in range(0, n-1):
if not reachable_a[m-1][j]:
reachable_a[m-1][j] = True
bfs(m-1, j, reachable_a)
coords = list()
for i in range(m):
for j in range(n):
if reachable_p[i][j] and reachable_a[i][j]:
coords.append([i, j])
return coords
