💬 Discord
Sign In
NeetCode #569LC-417MediumGraphsBlind 75NC 150NC 250
← Back to All Problems

#569 · #417 · Pacific Atlantic Water Flow(太平洋大西洋水流问题)

📌 Problem Statement & Constraints

There is an m x n rectangular island. The Pacific Ocean touches the left and top edges, the Atlantic the right and bottom edges. Given heights, return the coordinates of cells from which water can flow to both oceans. Water flows to a neighbour with height at most the current cell. Constraints: 1 <= m, n <= 200, 0 <= heights[i][j] <= 10^5.

💡 Core Algorithmic Approaches

  1. Reverse the flow direction: instead of flowing down from each cell, flow up from the ocean borders.
  2. A BFS/DFS from the Pacific border marks every cell that can reach the Pacific; likewise for the Atlantic.
  3. The intersection of the two reachable sets is the answer.
  4. This reverse-reachability trick turns an O((m*n)^2) search into O(m*n).

💻 Benchmark Python3 Implementation

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        from collections import deque
        m, n = len(heights), len(heights[0])

        def reachable(starts):
            seen = set(starts)
            q = deque(starts)
            while q:
                r, c = q.popleft()
                for dr, dc in ((0, 1), (0, -1), (1, 0), (-1, 0)):
                    nr, nc = r + dr, c + dc
                    if (0 <= nr < m and 0 <= nc < n and (nr, nc) not in seen
                            and heights[nr][nc] >= heights[r][c]):   # reverse flow: non-decreasing
                        seen.add((nr, nc))
                        q.append((nr, nc))
            return seen

        pacific = reachable([(i, 0) for i in range(m)] + [(0, j) for j in range(n)])
        atlantic = reachable([(i, n - 1) for i in range(m)] + [(m - 1, j) for j in range(n)])
        return [[r, c] for r, c in pacific & atlantic]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): each cell is visited at most twice.
💾 Space Complexity
O(m * n) for the two reachable sets.

⚠️ Interview Pitfalls & Follow-ups

  • Searching forward from every cell: O((m*n)^2) with repeated work.
  • Using > instead of >= in the reverse flow test: water can flow to an equal-height neighbour, so the reverse move must allow equality.
  • Only seeding the corners: the whole top/left edge is Pacific and the whole bottom/right edge is Atlantic.
  • Forgetting that the corners belong to both oceans: the set intersection handles it automatically.