Pacific Atlantic Water Flow

Intuition

Solution

class Solution:
    def _dfs(self, matrix, visited, i, j):
        if visited[i][j]:
            return
        visited[i][j] = True
        for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            if x < 0 or y < 0 or x >= len(matrix) or y >= len(matrix[0]):
                continue
            if matrix[x][y] < matrix[i][j]:
                continue
            self._dfs(matrix, visited, x, y)

    def pacificAtlantic(self, matrix: List[List[int]]) -> List[List[int]]:
        h = len(matrix)
        if h == 0:
            return []
        w = len(matrix[0])

        pacific = [[False] * w for _ in range(h)]
        for i in range(h):
            self._dfs(matrix, pacific, i, 0)
        for j in range(1, w):
            self._dfs(matrix, pacific, 0, j)

        atlantic = [[False] * w for _ in range(h)]
        for i in range(h):
            self._dfs(matrix, atlantic, i, w - 1)
        for j in range(w):
            self._dfs(matrix, atlantic, h - 1, j)

        ans = []
        for i in range(h):
            for j in range(w):
                if pacific[i][j] and atlantic[i][j]:
                    ans.append([i, j])
        return ans