MediumNo. 0417

Pacific Atlantic Water Flow — LeetCode 417 Python Solution

Topics
Depth-First Search, Breadth-First Search, Array, Matrix
On study lists
Blind 75 and NeetCode 150
Reading time
7 min

The problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

Example

Input
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]]
Output
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Explanation
The following cells can flow to the Pacific and Atlantic oceans, as shown below:

Python solution

PythonSolution
class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        def bfs(q: Deque[Tuple[int, int]], vis: List[List[bool]]) -> None:
            while q:
                x, y = q.popleft()
                for dx, dy in pairwise(dirs):
                    nx, ny = x + dx, y + dy
                    if (
                        0 <= nx < m
                        and 0 <= ny < n
                        and not vis[nx][ny]
                        and heights[nx][ny] >= heights[x][y]
                    ):
                        vis[nx][ny] = True
                        q.append((nx, ny))

        m, n = len(heights), len(heights[0])
        vis1 = [[False] * n for _ in range(m)]
        vis2 = [[False] * n for _ in range(m)]
        q1: Deque[Tuple[int, int]] = deque()
        q2: Deque[Tuple[int, int]] = deque()
        dirs = (-1, 0, 1, 0, -1)

        for i in range(m):
            q1.append((i, 0))
            vis1[i][0] = True
            q2.append((i, n - 1))
            vis2[i][n - 1] = True

        for j in range(n):
            q1.append((0, j))
            vis1[0][j] = True
            q2.append((m - 1, j))
            vis2[m - 1][j] = True

        bfs(q1, vis1)
        bfs(q2, vis2)

        return [(i, j) for i in range(m) for j in range(n) if vis1[i][j] and vis2[i][j]]

Complexity

Time
O(m × n)
Space · auxiliary
O(m × n)where m and n are the number of rows and columns in the matrix, respectively

Pattern: Matrix and Grid

Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 417. Pacific Atlantic Water Flow is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.

The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0130Surrounded RegionsMedium
0200Number of IslandsMedium
0463Island PerimeterEasy
0529MinesweeperMedium
0695Max Area of IslandMedium
0733Flood FillEasy

Frequently asked questions

How hard is LeetCode 417. Pacific Atlantic Water Flow?

LeetCode 417. Pacific Atlantic Water Flow is rated Medium on LeetCode.

What is the time complexity of LeetCode 417. Pacific Atlantic Water Flow?

The Python solution on this page runs in O(m × n).

What is the space complexity of LeetCode 417. Pacific Atlantic Water Flow?

The Python solution on this page uses O(m × n), where m and n are the number of rows and columns in the matrix, respectively auxiliary space.

What topics does LeetCode 417. Pacific Atlantic Water Flow cover?

LeetCode 417. Pacific Atlantic Water Flow is tagged Depth-First Search, Breadth-First Search, Array and Matrix on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.