Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Searching downhill from every cell repeats the same work. Instead, reverse the flow: start at an ocean and move to neighboring cells of equal or greater height. Every cell reached this way has a valid downhill path back to that ocean. Cells reached from both oceans are exactly the desired answer.

Approach

Start one breadth-first search from the top and left borders for the Pacific, and another from the bottom and right borders for the Atlantic.
Maintain a separate visited set for each search. From a queued cell, enqueue each unvisited neighbor whose height is at least the current height, marking it immediately. Equal heights are allowed because water can flow across level terrain.
Intersect the two visited sets. A coordinate in both has a downhill route to each ocean, possibly using different routes.
Return the intersection sorted by row and then column, matching the reference implementations' deterministic output.

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

        def bfs(source):
            q = deque()
            if source == 'p':
                for i in range(n): q.append((i, 0))
                for i in range(m): q.append((0, i))
            else:
                for i in range(n): q.append((i, m - 1))
                for i in range(m): q.append((n - 1, i))
            
            seen = set(q)
            while q:
                i, j = q.popleft()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if ni < 0 or nj < 0 or ni >= n or nj >= m: continue
                    if heights[ni][nj] >= heights[i][j] and not (ni, nj) in seen:
                        seen.add((ni, nj))
                        q.append((ni, nj))
            
            return seen
        
        setp = bfs('p')
        seta = bfs('a')

        return sorted(setp & seta)

Complexity analysis

Let K be the number of returned cells in an R × C grid. The two reverse breadth-first searches take O(RC) time, and sorting the K-cell intersection takes O(K log K), for O(RC + K log K) total time. Reachability and queue state use O(RC) auxiliary space, plus O(K) returned output.