Python DFS Recursion - Simple and Readable
Intuition\n\n- Instead of seeing how water can flow from land to the ocean, we can reverse our thinking and see how water can flow from ocean to land\n- Recursi
**Intuition**\n\n- Instead of seeing how water can flow from land to the ocean, we can reverse our thinking and see how water can flow from ocean to land\n- Recursive DFS helps keeps the code clean and readable\n- We try to traverse to a cell that is equal of higher than the previous cell\n- We perform DFS on all four sides, keeping track of coordinates reachable from both Pacific and Atlantic\n- Intersection of two sets of coordinates gives us our answer\n\n**Solution**\n```\nclass Solution:\n    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        m, n = len(heights), len(heights[0])\n        \n        def dfs(i: int, j: int, prev_height: int, coords: Set[Tuple[int]]) -> None:\n            if i < 0 or i == m or j < 0 or j == n:\n                # out of bounds\n                return\n            \n            if (i, j) in coords:\n                # already visited\n                return\n            \n            height = heights[i][j]\n            \n            if height < prev_height:\n                # water can\'t flow to a higher height\n                return\n            \n            # ocean is reachable from current coordinate\n            coords.add((i, j))\n            \n            # all four directions\n            dfs(i + 1, j, height, coords)\n            dfs(i - 1, j, height, coords)\n            dfs(i, j + 1, height, coords)\n            dfs(i, j - 1, height, coords)\n            \n        pacific_coords = set()\n        \n        # top row\n        for j in range(n):\n            dfs(0, j, 0, pacific_coords)\n        \n        # left col\n        for i in range(m):\n            dfs(i, 0, 0, pacific_coords)\n            \n        atlantic_coords = set()\n            \n        # right col\n        for i in range(m):\n            dfs(i, n - 1, 0, atlantic_coords)\n            \n        # bottom row\n        for j in range(n):\n            dfs(m - 1, j, 0, atlantic_coords)\n            \n        # intersection of coords reachable from both Pacific and Atlantic\n        return list(pacific_coords & atlantic_coords)\n```
['Depth-First Search', 'Recursion', 'Ordered Set', 'Python']