Pacific Atlantic Water Flow
Problem Description
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:
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.length
- n == heights[r].length
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 105
Solve it on LeetCode
Approaches
1. Brute Force Approach
The brute force approach involves considering each cell, checking if water can flow to both the Pacific and Atlantic oceans. We typically simulate water flow from each ocean and ensure they meet at every cell.
Intuition:
We try simulating water flow backwards, from the ocean to each cell, rather than from every cell to the ocean:
- For each cell in the matrix, check if a path exists to both oceans from that cell by simulating water flow.
- This involves invoking a recursive or iterative simulation for each cell.
However, this approach is inefficient in time complexity and not practical for larger matrices.
Approach:
- Iterate over each cell of the matrix.
- For each cell, perform a BFS or DFS to check if it can reach both oceans.
- Store the result and return all cells that satisfy the condition.
Code:
- Time Complexity: O(MN)^2) due to checking each cell and simulating the BFS/DFS for all cells.
- Space Complexity: O(MN) for the visited matrix used in each BFS/DFS.
2. DFS Approach
Instead of simulating water flow from every cell, simulate it from the oceans onto the grid and determine where flows intersect.
Intuition:
- Simulate water flowing from the oceans to the cells.
- Use DFS from the borders and mark which cells can reach each ocean.
- Cells reached by both DFS simulations represent meeting points.
Approach:
- Create two boolean matrices to track cells reachable by the Pacific and Atlantic oceans.
- Perform DFS from the Pacific-edge cells (top and left edges).
- Perform DFS from the Atlantic-edge cells (bottom and right edges).
- Collect all cells that are reachable by both sets of DFS calls.
Code:
- Time Complexity: O(MN), since each cell is processed twice (once for each ocean).
- Space Complexity: O(MN) for the space used by the two ocean-reachability matrices.
3. BFS Approach
We can use a BFS strategy instead of DFS by initializing queues with the coastal cells and expanding outwards.
Intuition:
- Start BFS from both borders simultaneously.
- Use queues to manage cells being processed for each ocean.
- A cell can flow to both oceans if it is found reachable by both BFS traversals.
Approach:
- Initialize two queues; one for each ocean’s border cells.
- Process each queue, marking cells as reachable if they meet the criteria.
- End conditions and new cells are appended based on water flowing constraints.
- Collect meeting points of both BFS traversals.
Code:
- Time Complexity: O(MN), as every cell is being processed twice using BFS.
- Space Complexity: O(MN) due to the storage requirements for the reachability matrices and queues.