There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.
The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).
The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.
Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.
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]]
Explanation: 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]] Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.
Constraints:
m == heights.lengthn == heights[r].length1 <= m, n <= 2000 <= heights[r][c] <= 105This approach involves performing a DFS from the cells adjacent to the Pacific and Atlantic oceans separately to determine reachable cells for each ocean and then finding their intersection.
The Pacific Ocean can be reached from any cell on the top row or leftmost column. Similarly, the Atlantic Ocean can be reached from any cell on the bottom row or rightmost column. We perform DFS from these boundary cells to mark all cells that can flow into the corresponding ocean. Finally, the intersection of these two sets gives cells that can reach both oceans.
The above function defines a DFS method and applies it from each pacific and atlantic border cell. For pacific, it applies DFS from top row and left column, while for atlantic, it's from bottom row and right column.
DFS explores in four directions, making recursive calls when conditions are satisfied, and keeps track of reachable cells using sets.
Java
C++
JavaScript
C#
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is processed once for each ocean.
Space Complexity: O(m * n), as sets used to keep track of visited cells for both oceans.
Instead of DFS, we can use BFS to achieve a similar result. This involves starting from the ocean-bordering cells and performing a level-order traversal to mark reachable cells, iteratively checking neighbors in a queue-based manner. BFS might be preferred in scenarios where recursion depth in DFS isn't ideal or could lead to stack overflow.
The idea is to initiate BFS from each ocean's boundary simultaneously, progressively marking each reachable cell, and determining intersecting positions for final results.
This function uses a deque to implement BFS from both Pacific and Atlantic borders. Starting points are defined for each ocean, and a queue processes each cell, enqueuing adjacent cells that retain valid flow conditions.
The results are gathered similarly by intersecting valid Pacific and Atlantic reachable positions.
Java
C++
Time Complexity: O(m * n), where BFS is performed from a subset of cells and checks neighbors iteratively.
Space Complexity: O(m * n), contingent upon queue operations and reachability matrices.
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) Approach | Time Complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is processed once for each ocean. Space Complexity: O(m * n), as sets used to keep track of visited cells for both oceans. |
| Breadth-First Search (BFS) Approach | Time Complexity: O(m * n), where BFS is performed from a subset of cells and checks neighbors iteratively. Space Complexity: O(m * n), contingent upon queue operations and reachability matrices. |
Pacific Atlantic Water Flow - Leetcode 417 - Python • NeetCode • 218,994 views views
Watch 9 more video solutions →Practice Pacific Atlantic Water Flow with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor