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 \times n).

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

The Python solution on this page uses O(m \times 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.

Pacific Atlantic Water Flow — LeetCode 417 Python Solution

MediumDepth-First SearchBreadth-First SearchArrayMatrix

Problem: #417
Pattern: Matrix and Grid
Reading time: 7 min
Source: leetcode.com

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

Python

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

Measure	Complexity
Time	O(m \times n)
Space	O(m \times n), where m and n are the number of rows and columns in the matrix, respectively auxiliary

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.

On study lists

This problem is on Blind 75 and NeetCode 150.

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 \times n).
What is the space complexity of LeetCode 417. Pacific Atlantic Water Flow?: The Python solution on this page uses O(m \times 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.