Skip to main content

417. Pacific Atlantic Water Flow

https://leetcode.com/problems/pacific-atlantic-water-flow/

Python​

DFS and Hash intersection​

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights or not heights[0]:
            return []

        m, n = len(heights), len(heights[0])
        offsets = [(1, 0), (0, 1), (-1, 0), (0, -1)]

        def dfs(row: int, col: int, reachable: set):
            reachable.add((row, col))

            for rx, cx in offsets:
                new_row, new_col = row+rx, col+cx

                if new_row < 0 or new_row >= m or new_col < 0 or new_col >= n:
                    continue

                if (new_row, new_col) in reachable:
                    continue

                if heights[new_row][new_col] < heights[row][col]:
                    continue
                dfs(new_row, new_col, reachable)

        pac_reachable, alt_reachable = set(), set()

        for row in range(m):
            dfs(row, 0, pac_reachable)
            dfs(row, n-1, alt_reachable)
        for col in range(n):
            dfs(0, col, pac_reachable)
            dfs(m-1, col, alt_reachable)

        return list(pac_reachable & alt_reachable)