#417

Medium

auto_awesomeArray plus Depth-First Search

LeetCode Problem Workspace

Pacific Atlantic Water Flow

Find all cells on an island where water can flow to both the Pacific and Atlantic oceans using DFS or BFS.

array depth first search breadth first search matrix

Problem Statement

You are given an m x n matrix heights representing an island, where each cell contains the height above sea level. The Pacific Ocean is located along the left and top edges of the grid, while the Atlantic Ocean touches the right and bottom edges. Water can flow from a cell to neighboring cells (north, south, east, west) if the neighboring cell has a height less than or equal to the current cell. The task is to find all cells where water can flow to both oceans.

The challenge requires identifying these specific cells by simulating water flow using Depth-First Search (DFS) or Breadth-First Search (BFS). Water from a cell adjacent to an ocean can flow into that ocean, and the objective is to determine all such cells. You need to output a list of grid cells where the water can flow to both the Pacific and Atlantic Oceans.

Examples

Example 1

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]]

The following cells can flow to the Pacific and Atlantic oceans, as shown below: [0,4]: [0,4] -> Pacific Ocean [0,4] -> Atlantic Ocean [1,3]: [1,3] -> [0,3] -> Pacific Ocean [1,3] -> [1,4] -> Atlantic Ocean [1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean [1,4] -> Atlantic Ocean [2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean [3,0]: [3,0] -> Pacific Ocean [3,0] -> [4,0] -> Atlantic Ocean [3,1]: [3,1] -> [3,0] -> Pacific Ocean [3,1] -> [4,1] -> Atlantic Ocean [4,0]: [4,0] -> Pacific Ocean [4,0] -> Atlantic Ocean Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans.

Example 2

Input: heights = [[1]]

Output: [[0,0]]

The water can flow from the only cell to the Pacific and Atlantic oceans.

Constraints

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105

Solution Approach

DFS Approach

Using DFS, we can start from the edges of both oceans and propagate the reachable cells inward. For the Pacific Ocean, start DFS from the top and left edges, and for the Atlantic Ocean, start DFS from the right and bottom edges. Mark the cells that can reach either ocean and then find the intersection of these two sets of cells to determine which cells can flow to both oceans.

BFS Approach

Similar to DFS, BFS can be used by first identifying all the cells that can reach the Pacific and Atlantic oceans. Start BFS from the borders of both oceans, expanding outward to neighboring cells. As BFS progresses, cells that can flow into both oceans are recorded. Finally, find the common cells in the two BFS result sets.

Optimized Space Usage

While DFS and BFS both have similar time complexities, space optimization can be achieved by utilizing in-place marking of cells. Instead of storing separate visited arrays for each ocean, use a combined approach that marks cells that can reach either ocean during the same DFS/BFS traversal. This reduces memory overhead.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity for both DFS and BFS approaches is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because each cell is visited once during the search. Space complexity is also O(m * n) due to the need to store the visited cells for both oceans.

What Interviewers Usually Probe

The problem requires familiarity with DFS/BFS traversal techniques and understanding grid-based problems.
A candidate should demonstrate the ability to efficiently mark cells that can flow to both oceans.
Look for candidates who understand the trade-offs between DFS and BFS, particularly with respect to space optimization.

Common Pitfalls or Variants

Common pitfalls

Not considering edge cases, such as the smallest grid or a single row/column island.
Confusing the direction of flow – ensure that water can flow in all four directions (up, down, left, right).
Misunderstanding the intersection of reachable cells for both oceans – both DFS/BFS must be executed separately for each ocean before finding the overlap.

Follow-up variants

What if the grid is much larger? Consider optimizing the space usage or processing multiple test cases efficiently.
What if diagonal movement is allowed for water flow? Adjust the DFS/BFS approach to account for diagonal directions.
What if there are additional height constraints for the water flow? Modify the DFS/BFS to account for specific thresholds for height differences.

FAQ

What is the time complexity of the Pacific Atlantic Water Flow problem?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid.

How does DFS help in solving this problem?

DFS helps by recursively visiting all the cells that can reach the ocean, marking them as reachable for Pacific and Atlantic oceans.

Can BFS be used instead of DFS for this problem?

Yes, BFS can also be used. It iterates over cells level by level, marking cells that can reach the oceans similarly to DFS.

What is the space complexity for this problem?

The space complexity is O(m * n), mainly due to the need to store the visited status of cells for both oceans.

Are there any edge cases to consider for this problem?

Yes, edge cases include the smallest grid, such as a 1x1 grid, or a grid where all cells have the same height.

terminal

Solution

Solution 1: BFS

We can start from the boundaries of the Pacific and Atlantic oceans and perform breadth-first search (BFS) respectively to find all cells that can flow to the Pacific and Atlantic oceans. Finally, we take the intersection of the two results, which represents cells that can flow to both the Pacific and Atlantic oceans.

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]]

Continue Practicing

#463 island perimeter #329 longest increasing path in a matrix #529 minesweeper