Python | BFS
Intuition\n- BFS from cells that are beside pacific ocean to find reachable cells.\n- BFS from cells that are beside atlantic ocean to find reachable cells.\n- 
# Intuition\n- BFS from cells that are beside pacific ocean to find reachable cells.\n- BFS from cells that are beside atlantic ocean to find reachable cells.\n- Take the intersection of the reachable cells to get cells that can reach both oceans.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.  First, create the starting queues for BFS by adding cells beside ocean.\n    - `pacificQueue` takes those cells with `row == 0` and `col == 0`\n    - `atlanticQueue` takes those cells with `row == ROWS - 1` and `cols == COLS - 1`\n    - Add their `level` from `heights` as a third param in the tuple\n1.  Perform BFS on each `queue` (Use a function)\n    - Create a `reachable` set\n    - For each cell, go through the adjacent cells\n    - If cell is in bounds, not in `reachable` set and has `height` greater than the `level` of the current cell, we add it to the `queue`.\n    - Notice we add all the popped cells to `reachable` set as from our previous condition, we only add reachable cells to the `reachable` set.\n    - Return the `reachable` set\n1.  Get the intersection of the `atlanticReachable` and `pacificReachable` sets to get the cells that can reach both oceans. Remember to return as a `list`\n\n# Complexity\n- Time complexity: `O(M*N)`\n- Space complexity: `O(M*N)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        ROWS, COLS = len(heights), len(heights[0])\n        \n        pacificQueue, atlanticQueue = deque(), deque()\n        \n        for col in range(COLS):\n            pacificQueue.append((0, col, heights[0][col]))\n            atlanticQueue.append((ROWS-1, col, heights[ROWS-1][col]))\n        \n        for row in range(ROWS):\n            pacificQueue.append((row, 0, heights[row][0]))\n            atlanticQueue.append((row, COLS-1, heights[row][COLS-1]))\n        \n        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]\n        \n        def bfs(queue):\n            reachable = set()\n            while queue:\n                for _ in range(len(queue)):\n                    r, c, level = queue.popleft()\n                    reachable.add((r, c))\n\n                    for dr, dc in directions:\n                        nr, nc = r + dr, c + dc\n\n                        if (nr < 0 or nr >= ROWS or \n                            nc < 0 or nc >= COLS or \n                            heights[nr][nc] < level or \n                            (nr, nc) in reachable):\n                            continue\n\n                        queue.append((nr, nc, heights[nr][nc]))\n            return reachable\n                    \n        atlanticReachable = bfs(atlanticQueue)\n        pacificReachable = bfs(pacificQueue)\n\n        return list(atlanticReachable.intersection(pacificReachable))\n```\n\n### Bonus: DFS Approach\n```\nclass Solution:\n    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n        ROWS, COLS = len(heights), len(heights[0])\n        \n        def dfs(r, c, prev_height):\n            if r < 0 or c < 0 or r == ROWS or c == COLS or heights[r][c] < prev_height or (r, c) in reachable:\n                return\n            reachable.add((r, c))\n            for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n                dfs(r + dr, c + dc, heights[r][c])\n        \n        reachable = set()\n        for r in range(ROWS):\n            for c in range(COLS):\n                if r == 0 or c == 0:\n                    dfs(r, c, -1)\n        pacific_reachable = reachable\n        \n        reachable = set()\n        for r in range(ROWS):\n            for c in range(COLS):\n                if r == ROWS - 1 or c == COLS - 1:\n                    dfs(r, c, -1)\n        atlantic_reachable = reachable\n        \n        return list(pacific_reachable.intersection(atlantic_reachable))\n```
['Python', 'Python3']