# LeetCode 417: Pacific Atlantic Water Flow ## Problem Restatement We are given an `m x n` matrix `heights`. Each cell represents land height. Water can flow from one cell to another adjacent cell if the next cell has height less than or equal to the current cell. Adjacent means four directions only: ```python up, down, left, right ``` The Pacific Ocean touches the top and left edges. The Atlantic Ocean touches the bottom and right edges. Return all coordinates `[r, c]` where water can flow to both oceans. The constraints are `1 <= m, n <= 200` and `0 <= heights[r][c] <= 10^5`. The source examples include `heights = [[1]]`, whose output is `[[0,0]]`. ## Input and Output | Item | Meaning | |---|---| | Input | Matrix `heights` | | Output | List of coordinates `[r, c]` | | Pacific border | Top row and left column | | Atlantic border | Bottom row and right column | | Flow rule | Water flows to equal or lower height | | Movement | Four directions only | Example function shape: ```python def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]: ... ``` ## Examples Example 1: ```python heights = [ [1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4], ] ``` One valid output is: ```python [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] ``` For example, cell `[2, 2]` has height `5`. It can flow toward the Pacific through a path that reaches the top or left edge. It can also flow toward the Atlantic through a path that reaches the bottom or right edge. Example 2: ```python heights = [[1]] ``` The answer is: ```python [[0, 0]] ``` The only cell touches both oceans. ## First Thought: Search From Every Cell A direct approach is to start a DFS or BFS from every cell. For each cell, simulate water flowing downhill or flat: ```python next_height <= current_height ``` If the search reaches the Pacific border and the Atlantic border, include the cell. This is correct, but it repeats too much work. A grid can have up to: ```python 200 * 200 = 40000 ``` cells. Starting a traversal from every cell can become expensive. ## Key Insight Reverse the direction. Instead of asking: ```text Can this cell flow to the ocean? ``` ask: ```text Which cells can reach this ocean if we walk backward? ``` Original water flow goes from high to low: ```python neighbor_height <= current_height ``` Reverse traversal goes from low to high: ```python neighbor_height >= current_height ``` Start from all Pacific-border cells and walk uphill or flat. Every cell reached this way can flow down to the Pacific. Do the same from all Atlantic-border cells. The answer is the intersection of both reachable sets. ## Algorithm Create two boolean matrices: | Matrix | Meaning | |---|---| | `pacific` | Cell can flow to the Pacific | | `atlantic` | Cell can flow to the Atlantic | Run DFS from all Pacific-border cells: ```python top row left column ``` Run DFS from all Atlantic-border cells: ```python bottom row right column ``` In reverse DFS, from cell `(r, c)`, move to neighbor `(nr, nc)` only if: ```python heights[nr][nc] >= heights[r][c] ``` After both traversals, collect every cell where: ```python pacific[r][c] and atlantic[r][c] ``` ## Correctness A cell can flow to the Pacific if there exists a path from that cell to a Pacific border where heights never increase along the water-flow direction. If we reverse that path, it starts from the Pacific border and moves through heights that never decrease. That is exactly what the reverse DFS allows: ```python next_height >= current_height ``` So every cell marked by the Pacific reverse traversal can flow to the Pacific. The same reasoning applies to the Atlantic traversal. A cell can flow to both oceans exactly when it appears in both reachable sets. The algorithm returns precisely those cells. Therefore, the returned coordinate list is correct. ## Complexity | Metric | Value | Why | |---|---|---| | Time | `O(mn)` | Each cell is visited at most once per ocean | | Space | `O(mn)` | Two visited matrices and recursion stack | Here `m` is the number of rows and `n` is the number of columns. ## Implementation ```python from typing import List class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: m = len(heights) n = len(heights[0]) pacific = [[False] * n for _ in range(m)] atlantic = [[False] * n for _ in range(m)] directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] def dfs(r: int, c: int, visited: list[list[bool]]) -> None: visited[r][c] = True for dr, dc in directions: nr = r + dr nc = c + dc if nr < 0 or nr >= m or nc < 0 or nc >= n: continue if visited[nr][nc]: continue if heights[nr][nc] < heights[r][c]: continue dfs(nr, nc, visited) for r in range(m): dfs(r, 0, pacific) dfs(r, n - 1, atlantic) for c in range(n): dfs(0, c, pacific) dfs(m - 1, c, atlantic) answer = [] for r in range(m): for c in range(n): if pacific[r][c] and atlantic[r][c]: answer.append([r, c]) return answer ``` ## Code Explanation We create two visited matrices: ```python pacific = [[False] * n for _ in range(m)] atlantic = [[False] * n for _ in range(m)] ``` A `True` value means the cell can reach that ocean. The DFS marks cells by reverse flow: ```python def dfs(r: int, c: int, visited: list[list[bool]]) -> None: ``` When visiting a cell, we mark it: ```python visited[r][c] = True ``` Then we inspect its four neighbors. A neighbor outside the grid is ignored. A neighbor already visited is ignored. A neighbor lower than the current cell is ignored: ```python if heights[nr][nc] < heights[r][c]: continue ``` This condition enforces reverse flow. We can only move to equal or higher cells. Then we start DFS from the ocean borders. Pacific: ```python dfs(r, 0, pacific) dfs(0, c, pacific) ``` Atlantic: ```python dfs(r, n - 1, atlantic) dfs(m - 1, c, atlantic) ``` Finally, we collect cells reachable from both: ```python if pacific[r][c] and atlantic[r][c]: answer.append([r, c]) ``` ## Iterative BFS Version The same idea can be written with BFS to avoid recursion depth concerns. ```python from collections import deque from typing import List class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: m = len(heights) n = len(heights[0]) def bfs(starts: list[tuple[int, int]]) -> list[list[bool]]: visited = [[False] * n for _ in range(m)] queue = deque() for r, c in starts: if not visited[r][c]: visited[r][c] = True queue.append((r, c)) directions = [(1, 0), (-1, 0), (0, 1), (0, -1)] while queue: r, c = queue.popleft() for dr, dc in directions: nr = r + dr nc = c + dc if nr < 0 or nr >= m or nc < 0 or nc >= n: continue if visited[nr][nc]: continue if heights[nr][nc] < heights[r][c]: continue visited[nr][nc] = True queue.append((nr, nc)) return visited pacific_starts = [] atlantic_starts = [] for r in range(m): pacific_starts.append((r, 0)) atlantic_starts.append((r, n - 1)) for c in range(n): pacific_starts.append((0, c)) atlantic_starts.append((m - 1, c)) pacific = bfs(pacific_starts) atlantic = bfs(atlantic_starts) return [ [r, c] for r in range(m) for c in range(n) if pacific[r][c] and atlantic[r][c] ] ``` ## Testing ```python def normalize(items): return sorted(map(tuple, items)) def test_pacific_atlantic(): s = Solution() result1 = s.pacificAtlantic([ [1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4], ]) expected1 = [ [0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0], ] assert normalize(result1) == normalize(expected1) assert s.pacificAtlantic([[1]]) == [[0, 0]] result3 = s.pacificAtlantic([ [1, 2], [4, 3], ]) assert normalize(result3) == normalize([[0, 1], [1, 0], [1, 1]]) result4 = s.pacificAtlantic([ [1, 1], [1, 1], ]) assert normalize(result4) == normalize([[0, 0], [0, 1], [1, 0], [1, 1]]) print("all tests passed") ``` ## Test Notes | Test | Why | |---|---| | Standard matrix | Checks normal multi-path behavior | | `[[1]]` | Single cell touches both oceans | | `2 x 2` matrix | Checks small border-heavy grid | | All equal heights | Every cell can flow to both oceans |