MediumBlind75MatrixDFSBFS
Pacific Atlantic Water Flow
Given an m x n matrix of heights, return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.
Examples
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]]
Water from these cells can flow to both oceans.
Input
heights = [[2,1],[1,2]]
Output
[[0,0],[0,1],[1,0],[1,1]]
All cells can flow to both oceans.
Constraints
- •
m == heights.length - •
n == heights[r].length - •
1 <= m, n <= 200 - •
0 <= heights[r][c] <= 10^5
Approaches
For each cell, BFS to check if it can reach both oceans.
CodeT: O(m^2 * n^2) | S: O(m * n)
from collections import deque
def pacific_atlantic(heights):
if not heights:
return []
rows, cols = len(heights), len(heights[0])
result = []
def bfs(start_r, start_c):
pacific = atlantic = False
visited = set()
queue = deque([(start_r, start_c)])
visited.add((start_r, start_c))
while queue:
r, c = queue.popleft()
if r == 0 or c == 0:
pacific = True
if r == rows - 1 or c == cols - 1:
atlantic = True
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and heights[nr][nc] <= heights[r][c]:
visited.add((nr, nc))
queue.append((nr, nc))
return pacific and atlantic
for i in range(rows):
for j in range(cols):
if bfs(i, j):
result.append([i, j])
return resultBFS from Pacific and Atlantic ocean borders, then find intersection.
CodeT: O(m * n) | S: O(m * n)
from collections import deque
def pacific_atlantic(heights):
if not heights:
return []
rows, cols = len(heights), len(heights[0])
def bfs(starts):
visited = set(starts)
queue = deque(starts)
while queue:
r, c = queue.popleft()
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in visited and heights[nr][nc] >= heights[r][c]:
visited.add((nr, nc))
queue.append((nr, nc))
return visited
pacific = set()
atlantic = set()
for i in range(rows):
pacific.add((i, 0))
atlantic.add((i, cols - 1))
for j in range(cols):
pacific.add((0, j))
atlantic.add((rows - 1, j))
p_reach = bfs(pacific)
a_reach = bfs(atlantic)
return [list(coord) for coord in p_reach & a_reach]Same reverse approach using DFS instead of BFS.
Diagram
BFS from ocean borders:
Pacific starts: top row and left column
Atlantic starts: bottom row and right column
Intersection of reachable cells: [[0,4],[1,3],...]
CodeT: O(m * n) | S: O(m * n)
def pacific_atlantic(heights):
if not heights:
return []
rows, cols = len(heights), len(heights[0])
pacific = set()
atlantic = set()
def dfs(r, c, visited, prev_height):
if (r, c) in visited or r < 0 or r >= rows or c < 0 or c >= cols or heights[r][c] < prev_height:
return
visited.add((r, c))
for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
dfs(r + dr, c + dc, visited, heights[r][c])
for i in range(rows):
dfs(i, 0, pacific, heights[i][0])
dfs(i, cols - 1, atlantic, heights[i][cols - 1])
for j in range(cols):
dfs(0, j, pacific, heights[0][j])
dfs(rows - 1, j, atlantic, heights[rows - 1][j])
return [[r, c] for r, c in pacific & atlantic]Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force - BFS per Cell | O(m^2 * n^2) | O(m * n) | For each cell, BFS to check if it can reach both oceans. |
| Reverse BFS from Oceans | O(m * n) | O(m * n) | BFS from Pacific and Atlantic ocean borders, then find intersection. |
| Optimized Reverse DFS | O(m * n) | O(m * n) | Same reverse approach using DFS instead of BFS. |
Brute Force - BFS per Cell
T: O(m^2 * n^2)S: O(m * n)
For each cell, BFS to check if it can reach both oceans.
Reverse BFS from Oceans
T: O(m * n)S: O(m * n)
BFS from Pacific and Atlantic ocean borders, then find intersection.
Optimized Reverse DFS
T: O(m * n)S: O(m * n)
Same reverse approach using DFS instead of BFS.
Common Mistakes
BFS from each cell instead of reverse BFS from oceans
Not handling the height comparison correctly (water flows to equal or lower)
Forgetting to check all four directions