LeetCode 417 Pacific Atlantic Water Flow - Implementation

DFS from ocean borders, find intersection.

function pacificAtlantic(heights): m, n = len(heights), len(heights[0]) pacific = set() atlantic = set()

def dfs(r, c, visited):
    if (r, c) in visited:
        return
    visited.add((r, c))
    for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
        nr, nc = r + dr, c + dc
        if 0 <= nr < m and 0 <= nc < n and heights[nr][nc] >= heights[r][c]:
            dfs(nr, nc, visited)

for c in range(n):
    dfs(0, c, pacific)
    dfs(m-1, c, atlantic)
for r in range(m):
    dfs(r, 0, pacific)
    dfs(r, n-1, atlantic)

return list(pacific & atlantic)

$O(m \cdot n)$ time and space.