How do you solve Pacific Atlantic Water Flow on LeetCode?

Pacific Atlantic Water Flow (LeetCode #417) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: Water can flow to neighboring cells only if the neighboring cell's height is less than or equal to the current cell's height.

What is the time complexity of Pacific Atlantic Water Flow?

The optimal solution for Pacific Atlantic Water Flow runs in O(m * n) time and uses O(m * n) space. This complexity is efficient because each cell is visited once during the DFS for both oceans.

What is the brute force solution for Pacific Atlantic Water Flow?

The brute force approach for Pacific Atlantic Water Flow is Brute Force, with O(m * n * (m + n)) time complexity and O(m * n) space complexity. The brute force approach checks each cell to see if water can flow to both oceans by performing a depth-first search (DFS) from that cell. This is straightforward but inefficient, as it may repeat calculations for cells multiple times. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve Pacific Atlantic Water Flow?

Pacific Atlantic Water Flow uses the following concepts: Array, Depth-First Search, Breadth-First Search, Matrix. The recommended patterns to study are: Depth-First Search (DFS), Breadth-First Search (BFS), Graph Traversal.

What are the interview tips for Pacific Atlantic Water Flow?

Clearly explain your thought process and the reasoning behind your approach. Consider edge cases and discuss them with the interviewer. Be prepared to optimize your solution after presenting the brute force approach.

What are common mistakes when solving Pacific Atlantic Water Flow?

Not considering edge cases like empty matrices or single row/column matrices. Failing to correctly implement the DFS logic, especially in marking cells.

#417

Pacific Atlantic Water Flow

Medium

ArrayDepth-First SearchBreadth-First SearchMatrixDepth-First Search (DFS)Breadth-First Search (BFS)Graph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(m * n * (m + n))	O(m * n)
Space	O(m * n)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

The optimal solution uses a reverse approach by starting from the oceans and performing a DFS or BFS to mark reachable cells. This way, we only traverse each cell once, making it more efficient.

⚙️

Algorithm

4 steps

1Step 1: Initialize two boolean matrices for Pacific and Atlantic ocean reachability.
2Step 2: Perform DFS from all cells adjacent to the Pacific Ocean and mark reachable cells.
3Step 3: Perform DFS from all cells adjacent to the Atlantic Ocean and mark reachable cells.
4Step 4: Collect all cells that are marked reachable by both oceans.

solution.py30 lines

1# Full working Python code
2from typing import List
3
4def pacificAtlantic(heights: List[List[int]]) -> List[List[int]]:
5    if not heights:
6        return []
7    m, n = len(heights), len(heights[0])
8    result = []
9    pacific = [[False] * n for _ in range(m)]
10    atlantic = [[False] * n for _ in range(m)]
11
12    def dfs(r, c, visited):
13        visited[r][c] = True
14        for dr, dc in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
15            nr, nc = r + dr, c + dc
16            if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] and heights[nr][nc] >= heights[r][c]:
17                dfs(nr, nc, visited)
18
19    for i in range(m):
20        dfs(i, 0, pacific)
21        dfs(i, n - 1, atlantic)
22    for j in range(n):
23        dfs(0, j, pacific)
24        dfs(m - 1, j, atlantic)
25
26    for i in range(m):
27        for j in range(n):
28            if pacific[i][j] and atlantic[i][j]:
29                result.append([i, j])
30    return result

ℹ

Complexity note: This complexity is efficient because each cell is visited once during the DFS for both oceans.

1Water can flow to neighboring cells only if the neighboring cell's height is less than or equal to the current cell's height.
2Starting from the oceans allows us to efficiently mark all reachable cells without redundant checks.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.