Pacific Atlantic Water Flow
Problem Statement
You are given a rectangular island heights
where heights[r][c]
represents the height above sea level of the cell at coordinate (r, c)
.
The islands borders the Pacific Ocean from the top and left sides, and borders the Atlantic Ocean from the bottom and right sides.
Water can flow in four directions (up, down, left, or right) from a cell to a neighboring cell with height equal or lower. Water can also flow into the ocean from cells adjacent to the ocean.
Find all cells where water can flow from that cell to both the Pacific and Atlantic oceans. Return it as a 2D list where each element is a list [r, c]
representing the row and column of the cell. You may return the answer in any order.
Example 1:
Input: heights = [ [4,2,7,3,4], [7,4,6,4,7], [6,3,5,3,6]]
Output: [[0,2],[0,4],[1,0],[1,1],[1,2],[1,3],[1,4],[2,0]]
Example 2:
Input: heights = [[1],[1]]
Output: [[0,0],[0,1]]
Constraints:
1 <= heights.length, heights[r].length <= 100
0 <= heights[r][c] <= 1000
You should aim for a solution with O(m * n)
time and O(m * n)
space, where m
is the number of rows and n
is the number of columns in the grid.
Recommended Time and Space Complexity
You should aim for a solution with O(m * n)
time and O(m * n)
space, where m
is the number of rows and n
is the number of columns in the grid.
Hint 1
A brute force solution would be to traverse each cell in the grid and run a BFS from each cell to check if it can reach both oceans. This would result in an O((m * n)^2)
solution. Can you think of a better way? Maybe you should consider a reverse way of traversing.
Hint 2
We can use the Depth First Search (DFS) algorithm starting from the border cells of the grid. However, we reverse the condition such that the next visiting cell should have a height greater than or equal to the current cell. For the top and left borders connected to the Pacific Ocean, we use a hash set called pacific
and run a DFS from each of these cells, visiting nodes recursively. Similarly, for the bottom and right borders connected to the Atlantic Ocean, we use a hash set called atlantic
and run a DFS. The required coordinates are the cells that exist in both the pacific
and atlantic
sets. How do you implement this?
Hint 3
We perform DFS from the border cells, using their respective hash sets. During the DFS, we recursively visit the neighbouring cells that are unvisited and have height greater than or equal to the current cell’s height and add the current cell’s coordinates to the corresponding hash set. Once the DFS completes, we traverse the grid and check if a cell exists in both the hash sets. If so, we add that cell to the result list.
Solution
Brute Force (Backtracking)
def pacific_atlantic(heights: List[List[int]]) -> List[List[int]]: rows, cols = len(heights), len(heights[0]) directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def can_reach_both_oceans(row, col): pacific = False atlantic = False
def dfs(r, c, prev_val): nonlocal pacific, atlantic if r < 0 or c < 0: pacific = True return if r >= rows or c >= cols: atlantic = True return if heights[r][c] > prev_val: return
temp = heights[r][c] heights[r][c] = float('inf') for dr, dc in directions: dfs(r + dr, c + dc, temp) if pacific and atlantic: break heights[r][c] = temp
dfs(row, col, float('inf')) return pacific and atlantic
result = [] for r in range(rows): for c in range(cols): if can_reach_both_oceans(r, c): result.append([r, c]) return result
Time complexity: O(m * n * 4 ^ {m * n})
Space complexity: O(m * n)