A point P should have the following two properties if it is included in the returned array:
- There is an non-decreasing path from a coast point of Pacific to P.
- There is an non-decreasing path from a coast point of Atlantic to P.
Here coast point means a point which is next to the oceans, which means the points in the first row and the first column are all coast points of Pacific, and the points in the last row and the last column are all coast points of Atlantic.
Therefore, we can compute the points that have the two properties respectively by running DFS / BFS twice, and return the points with both properties.
class Solution(object): def pacificAtlantic(self, matrix): """ :type matrix: List[List[int]] :rtype: List[List[int]] """ M = len(matrix) if M == 0: return  N = len(matrix) res =  visitedPac = [[False] * N for _ in range(M)] visitedAtl = [[False] * N for _ in range(M)] stackPac =  stackAtl =  # init with coast points for i in range(M): visitedPac[i] = True visitedAtl[i][N - 1] = True stackPac.append((i, 0)) stackAtl.append((i, N - 1)) for j in range(N): visitedPac[j] = True visitedAtl[M - 1][j] = True stackPac.append((0, j)) stackAtl.append((M - 1, j)) # dfs self.dfs(matrix, M, N, stackPac, visitedPac) self.dfs(matrix, M, N, stackAtl, visitedAtl) # combine for i in range(M): for j in range(N): if visitedPac[i][j] and visitedAtl[i][j]: res.append([i, j]) return res def dfs(self, matrix, M, N, stack, visited): dirs = [(0, 1), (1, 0), (0, -1), (-1, 0)] while stack: pos = stack.pop() for d in dirs: i = pos + d j = pos + d if 0 <= i < M and 0 <= j < N and not visited[i][j] and matrix[i][j] >= matrix[pos][pos]: visited[i][j] = True stack.append((i, j))