An m x n island has the Pacific Ocean touching its top and left edges and the Atlantic Ocean touching its bottom and right edges. heights[r][c] is the height of each cell. Rain water flows from a cell to a neighbour (up, down, left, right) if the neighbour's height is less than or equal to the current height, and flows into an ocean from any edge cell. Return the coordinates [r, c] of every cell from which water can reach both oceans, in any order.
[2,2] (height 5) water can go up and left to the Pacific and right and down to the Atlantic.- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10^5
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force runs a DFS from each cell to see which oceans it reaches, costing O((m * n)^2). Reverse the direction: water flows downhill from a cell to the ocean, so going uphill from the ocean finds every cell that can drain into it. Start a BFS from all Pacific edge cells and move to a neighbour only if it is at least as high; that marks every Pacific-reachable cell. Do the same from the Atlantic edges. Cells marked by both searches are the answer.
Algorithm
- Create two boolean grids:
pacandatl. - Start a BFS for the Pacific from every cell in the top row and left column.
- Start a BFS for the Atlantic from every cell in the bottom row and right column.
- In each BFS, move to a neighbour if it is unvisited and
heights[next] >= heights[cur]. - Collect every
[r, c]where bothpacandatlare true.
O(m * n)Space: O(m * n)<= instead of >= is the bug most people make here.class Solution: def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]: m, n = len(heights), len(heights[0])Β def bfs(starts): # Climb uphill from the ocean: move to neighbours at least as high seen = set(starts) queue = deque(starts) while queue: r, c = queue.popleft() for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)): if (0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen and heights[nr][nc] >= heights[r][c]): seen.add((nr, nc)) queue.append((nr, nc)) return seenΒ pac = bfs([(0, c) for c in range(n)] + [(r, 0) for r in range(1, m)]) atl = bfs([(m - 1, c) for c in range(n)] + [(r, n - 1) for r in range(m - 1)]) return [[r, c] for r in range(m) for c in range(n) if (r, c) in pac and (r, c) in atl]