LC 0417 [M] Pacific Atlantic Water Flow - ALawliet/algorithms GitHub Wiki
https://www.youtube.com/watch?v=s-VkcjHqkGI&ab_channel=NeetCode
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
ROWS = len(heights)
COLS = len(heights[0])
# visited sets for that ocean
pac = set()
atl = set()
def dfs(r, c, visit, prevHeight):
if ((r, c) in visit or r < 0 or c < 0 or r == ROWS or c == COLS or heights[r][c] < prevHeight):
return
visit.add((r, c))
dfs(r+1, c, visit, heights[r][c])
dfs(r-1, c, visit, heights[r][c])
dfs(r, c+1, visit, heights[r][c])
dfs(r, c-1, visit, heights[r][c])
for c in range(COLS):
dfs(0, c, pac, heights[0][c]) # pac top
dfs(ROWS-1, c, atl, heights[ROWS-1][c]) # atl bot
for r in range(ROWS):
dfs(r, 0, pac, heights[r][0]) # pac left
dfs(r, COLS-1, atl, heights[r][COLS-1]) # atl right
res = []
for r in range(ROWS):
for c in range(COLS):
if (r, c) in pac and (r, c) in atl:
res.append([r, c])
return res