[Python] Explaining Common Pitfalls and Nuanced Tricks Along with the Problem Patterns
1. Problem Statement Breakdown\n\nIn this problem, we are given a m x n matrix named heights, where each cell represents the height above sea level. The grid bo
### 1. Problem Statement Breakdown\n\nIn this problem, we are given a `m x n` matrix named `heights`, where each cell represents the height above sea level. The grid borders two oceans: the Pacific Ocean on the top and left edges, and the Atlantic Ocean on the right and bottom edges. The rule for water flow is that it can only move from a cell to another neighboring cell (north, south, east, or west) if the neighboring cell\'s height is less than or equal to the current cell\'s height. We need to find all cells from which water can flow to both oceans.\n\n### 2. Solution Rationale\n\nThe approach involves conducting depth-first searches (DFS) from the edges of the matrix that touch each ocean, marking cells as reachable from that ocean. Specifically, we start from the cells adjacent to the oceans and perform DFS, moving to adjacent cells if they are higher or equal in height. This process is done twice: once for the Pacific (top and left edges) and once for the Atlantic (right and bottom edges). The intersection of the cells reachable by both oceans is the solution.\n\n### 3. Python Code Explanation\n\nThe Python solution involves defining a DFS helper function and applying it to the edge cells for both oceans. The function marks visited cells and proceeds recursively to adjacent cells that meet the height requirement.\n\n```python\ndef pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:\n  \n    rows, cols = len(heights), len(heights[0])\n    pacific, atlantic = set(), set()\n\n    def dfs(r, c, visited, prev):\n        if not ((0 <= r < rows) and (0 <= c < cols)):\n            return \n        \n        if (r, c) in visited or heights[r][c] < prev:\n            return \n        \n        visited.add((r, c))\n        \n        directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]\n        for dr, dc in directions:\n            nr, nc = r + dr, c + dc\n            dfs(nr, nc, visited, heights[r][c])\n\n    for r in range(rows):\n        dfs(r, 0, pacific, heights[r][0])\n        dfs(r, cols-1, atlantic, heights[r][cols-1])\n    \n    for c in range(cols):\n        dfs(0, c, pacific, heights[0][c])\n        dfs(rows-1, c, atlantic, heights[rows-1][c])\n    \n    return list(pacific & atlantic)\n```\n\n\n\n### 4. Time and Space Complexity Analysis\n\n- **Time Complexity:** O(m*n) where m and n are the dimensions of the matrix. Each cell is visited at most twice (once for each ocean).\n- **Space Complexity:** O(m*n) for the storage of the visited sets and the recursion stack in the worst case.\n\n### 5. Common Pitfalls and Nuanced Tricks\n\n- **Pitfall:** Forgetting to check for previous height in DFS can lead to incorrect traversal. Passing some other value instead of calling first dfs with the value of the same row index and column index. \n- **Trick:** Using sets for visited cells for efficient lookup and avoiding duplicates.\n\n### 6. Problem Pattern\n\nThis problem is a classic example of graph traversal using Depth-First Search (DFS) from multiple sources (edge cells in this case). It demonstrates how to use DFS to propagate conditions (height constraints) through a grid.\n\n### 7. Similar LeetCode Problems\n\n- [200. Number of Islands](https://leetcode.com/problems/number-of-islands/)\n- [695. Max Area of Island](https://leetcode.com/problems/max-area-of-island/)\n- [130. Surrounded Regions](https://leetcode.com/problems/surrounded-regions/)\n\nEach of these problems involves traversing a grid with DFS or BFS, applying similar principles to different scenarios.
['Depth-First Search', 'Graph', 'Recursion', 'Python3']