Pacific Atlantic Water Flow
DESCRIPTION (credit Leetcode.com)
You are given an m x n matrix of non-negative integers representing a grid of land. Each value in the grid represents the height of that piece of land.
The Pacific Ocean touches the left and top edges of the matrix, while the Atlantic Ocean touches the right and bottom edges. Water can only flow from a cell to its neighboring cells directly north, south, east, or west, but only if the height of the neighboring cell is equal to or lower than the current cell.
Write a function to return a list of grid coordinates (i, j) where water can flow to both the Pacific and Atlantic Oceans. Water can flow from all cells directly adjacent to the ocean into that ocean.
EXAMPLES
Example 1:
Input:
grid = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]
Output:
[ [0, 2], [1, 2], [2, 0], [2, 1], [2, 2] ]
Run your code to see results here
Explanation
To solve this question, we need to traverse the grid to find all cells where water can flow to both the Pacific and Atlantic Oceans, and then find the cells that are contained in both those sets.
Approach 1: Brute Force Approach
Let's focus on how to find all the cells that are reachable from an ocean. One straightforward approach is to iterate over each cell in the graph, and then check if there is a valid path from that cell to the ocean. If there is, we can add it to a set (depending on if it reaches the Pacific or Atlantic Ocean). After iterating over each cell, we can return the intersection of those two sets.
class Solution:def pacificAtlantic(self, matrix):if not matrix or not matrix[0]:return []rows, cols = len(matrix), len(matrix[0])pacific = set()atlantic = set()# Try to find a path from r, c to the Pacific or Atlantic ocean# via neighboring cells with lower heightsdef dfs(start_r, start_c, r, c, visited):if (r, c) in visited:returnvisited[(r, c)] = Trueif r == 0 or c == 0:pacific.add((start_r, start_c))if r == rows - 1 or c == cols - 1:atlantic.add((start_r, start_c))directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]for dr, dc in directions:nr, nc = r + dr, c + dcif 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] <= matrix[r][c]:dfs(start_r, start_c, nr, nc, visited)visited[(nr, nc)] = False# Perform full DFS from each cell.for r in range(rows):for c in range(cols):visited = {}dfs(r, c, r, c, visited)return list(pacific & atlantic)
The problem with this approach is that it is very inefficient. For each cell, we have to perform a full DFS traversal of the entire grid in the worst case, resulting in a run-time of O((m x n)2).
Approach 2: Boundary DFS
The brute-force approach is inefficient because there is a lot of repeat work being done. For example, we have to calculate parts of the same path multiple times as we check if there is a valid path from a cell to the ocean.
A more efficient approach is to use "boundary DFS". With this approach, we "invert" the problem by starting from all cells adjacent to each ocean, and then use DFS to find cells that can flow into that cell. All the cells that we visit during each of these traversals are the set of cells that can flow into the ocean that the DFS originated from.
This is more efficient because it reduces redundant work - once we visit a cell using this traversal, we can mark it as visited so it is not visited by future traversals.
At the end, we can return the intersection of both sets to get the final answer.
Solution
class Solution:def pacific_atlantic_flow(self, grid):if not grid or not grid[0]:return []rows, cols = len(grid), len(grid[0])# Step 1: Initialize empty setspacific_reachable = set()atlantic_reachable = set()def dfs(r, c, reachable):reachable.add((r, c))for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:nr, nc = r + dr, c + dcif 0 <= nr < rows and 0 <= nc < cols:if (nr, nc) not in reachable and grid[nr][nc] >= grid[r][c]:dfs(nr, nc, reachable)# initializes DFS from all cells in the Atlantic and Pacific Oceans# Note how we share a single visited set# across DFS calls that originate from the same oceanfor r in range(rows):dfs(r, 0, pacific_reachable)dfs(r, cols - 1, atlantic_reachable)for c in range(cols):dfs(0, c, pacific_reachable)dfs(rows - 1, c, atlantic_reachable)# return the intersection of both sets.return list(pacific_reachable & atlantic_reachable)
Complexity Analysis
Time Complexity: In Approach #2, we visit each cell once aross all DFS calls that originate from a particular ocean, In the worst case, this means we visit each cell twice, for a total time complextiy of O(m * n). Space Complexity: O(m * n) for the two visited sets that we have to maintain for the DFS traversals.
Loading comments...