Q83: Pacific Atlantic Water Flow. - DSA Patterns (Multi-Lang)

In Simple Words: Work backwards from ocean borders: start from Pacific edges and run DFS inwards uphill (neighborHeight >= currentHeight); repeat from Atlantic edges. Cells visited by both oceans form answer.

Time: $O(M \cdot N)$ | Space: $O(M \cdot N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:
    rows, cols = len(heights), len(heights[0])
    pac, atl = set(), set()
    def dfs(r, c, visit, prev_h):
        if (r, c) in visit or r < 0 or c < 0 or r >= rows or c >= cols or heights[r][c] < prev_h:
            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])
        dfs(rows - 1, c, atl, heights[rows - 1][c])
    for r in range(rows):
        dfs(r, 0, pac, heights[r][0])
        dfs(r, cols - 1, atl, heights[r][cols - 1])

    return list(map(list, pac.intersection(atl)))