417: Time 96.50% and Space 94.12%, Solution with step by step explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n1. Check if the input matrix is empty. If it is, return an empty list.\n\
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n1. Check if the input matrix is empty. If it is, return an empty list.\n\n2. Determine the number of rows and columns in the input matrix.\n\n3. Create two visited matrices of the same size as the input matrix, one for each ocean.\n\n4. Create two empty queues, one for each ocean.\n\n5. Add all the cells in the first and last rows to the Pacific queue, and mark them as visited in the Pacific visited matrix. Add all the cells in the first and last columns to the Atlantic queue, and mark them as visited in the Atlantic visited matrix.\n\n6. Define a helper function, bfs, that takes a queue and a visited matrix as input, and runs a breadth-first search on the input matrix starting from the cells in the queue. The function visits each cell that can flow to the ocean and adds it to the queue.\n\n7. Run bfs on both oceans, starting from the boundary cells.\n\n8. Find the cells that can flow to both oceans by iterating through all cells in the input matrix, and adding the ones that are marked as visited in both the Pacific and Atlantic visited matrices to the result list.\n\n9. Return the result list.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\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        if not heights:\n            return []\n        \n        rows, cols = len(heights), len(heights[0])\n        \n        # Create visited matrices for both oceans\n        pacific_visited = [[False] * cols for _ in range(rows)]\n        atlantic_visited = [[False] * cols for _ in range(rows)]\n        \n        # Create queue for both oceans\n        pacific_queue = deque()\n        atlantic_queue = deque()\n        \n        # Add cells in the first and last rows to their respective queues\n        for col in range(cols):\n            pacific_queue.append((0, col))\n            atlantic_queue.append((rows-1, col))\n            pacific_visited[0][col] = True\n            atlantic_visited[rows-1][col] = True\n        \n        # Add cells in the first and last columns to their respective queues\n        for row in range(rows):\n            pacific_queue.append((row, 0))\n            atlantic_queue.append((row, cols-1))\n            pacific_visited[row][0] = True\n            atlantic_visited[row][cols-1] = True\n        \n        # Define helper function to check if a cell can flow to an ocean\n        def bfs(queue, visited):\n            while queue:\n                row, col = queue.popleft()\n                # Check adjacent cells\n                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:\n                    r, c = row + dr, col + dc\n                    # Check if cell is within bounds and hasn\'t been visited yet\n                    if 0 <= r < rows and 0 <= c < cols and not visited[r][c]:\n                        # Check if cell can flow to the ocean\n                        if heights[r][c] >= heights[row][col]:\n                            visited[r][c] = True\n                            queue.append((r, c))\n        \n        # Run BFS on both oceans starting from the boundary cells\n        bfs(pacific_queue, pacific_visited)\n        bfs(atlantic_queue, atlantic_visited)\n        \n        # Find the cells that can flow to both oceans\n        result = []\n        for row in range(rows):\n            for col in range(cols):\n                if pacific_visited[row][col] and atlantic_visited[row][col]:\n                    result.append([row, col])\n        \n        return result\n\n```
['Array', 'Depth-First Search', 'Breadth-First Search', 'Python', 'Python3']