Problem Statement in English

You’re given an m x n integer matrix heights representing the height of each unit cell in a continent.

The “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Approach

Solving the problem in the way the question pushes you towards results in some complications. Like, dealing with duplicates, and checking if a cell can reach both oceans. Instead, we can reverse the process.

We can start from the oceans and see which cells can reach them, using a plain BFS.

Solution in Python


class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        rows = len(heights)
        cols = len(heights[0])

        def bfs(l):
            seen = set()
            q = deque(l)

            while q:
                x,y = q.popleft()
                seen.add((x,y))

                for dx,dy in directions:
                    nx,ny = x+dx,y+dy

                    if (nx,ny) not in seen and 0 <= nx < rows and 0 <= ny < cols and heights[x][y] <= heights[nx][ny]:
                        q.append((nx,ny))

            return seen

        atlantic = []
        pacific = []

        # load rows
        for j in range(cols):
            atlantic.append((rows - 1, j))
            pacific.append((0, j))

        # load cols
        for i in range(rows):
            atlantic.append((i, cols - 1))
            pacific.append((i, 0))

        # calc
        a_from_p = bfs(pacific)
        p_from_a = bfs(atlantic)

        res = []

        for c in a_from_p:
            if c in p_from_a:
                res.append(c)

        return res

Complexity

  • Time: $O(m \times n)$
    Since we iterate over each cell once for each ocean.

  • Space: $O(m \times n)$
    Since we store the cells that can reach each ocean.

And we are done.