Watershed Divide

As know as Pacific Atlantic Waterflow

Intuition: take the reverse approach, start from the shores and go up. Both BFS and DFS should work.

m, n = len(heights), len(heights[0])
watershed_p = [[False for _ in range(n)] for _ in range(m)]
watershed_a = deepcopy(watershed_p)
 
def dfs(r, c, watershed) -> None:
    if watershed[r][c]:
        return
    watershed[r][c] = True
    offsets = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    for r_offset, c_offset in offsets:
        new_r, new_c = r + r_offset, c + c_offset
        if (
            0 <= new_r < m and 0 <= new_c < n and
            heights[new_r][new_c] >= heights[r][c]
        ):
            dfs(new_r, new_c, watershed)
 
shore_p = [(0, c) for c in range(n)] + [(r, 0) for r in range(m)]
shore_a = [(m - 1, c) for c in range(n)] + [(r, n - 1) for r in range(m)]
 
for r, c in shore_p:
    dfs(r, c, watershed_p)
 
for r, c in shore_a:
    dfs(r, c, watershed_a)
 
return [
    (r, c)
    for r, c in product(range(m), range(n))
    if watershed_p[r][c] and watershed_a[r][c]
]