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