Solutions

1. For each grid (i, j), do BFS twice for both Pacific and Atlantic flow: O(n^4)
2. For each grid (i, j), do BFS twice, but this time, can stop on grids already visited: slightly better
3. For each grid (i, j) on each coastline, do BFS and return the grids that visited from both: O(n^3)

Algorithm

1. Initialize m ⅹ n matrix flow_p, flow_a <- False.
2. 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].
3. For each coastline (i, j) of Atlantic, do BFS (same but flow_a)
4. 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]): # ascending route
                        reachable[x][y] = True
                        queue.append((x, y))

        # pacific
        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)

        # atlantic
        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)

        # merge
        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