Pacific Atlantic Water Flow
Problem Statement
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.
Constraints:
- m == heights.length
- n == heights[r].length
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 10^5
Input Format:
- An m x n integer matrix heights
Output Format:
- A 2D list of grid coordinates where water can flow to both oceans
Examples:
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 both the Pacific and Atlantic oceans: [0,4], [1,3], [1,4], [2,2], [3,0], [3,1], [4,0].
Example 2:
Input:
heights = [[2,1],[1,2]]
Output:
[[0,0],[0,1],[1,0],[1,1]]
Explanation:
The following cells can flow to both the Pacific and Atlantic oceans: [0,0], [0,1], [1,0], [1,1].
Solutions
DFS Approach
Use DFS to find all cells that can reach each ocean. Start DFS from the borders of the matrix (which are adjacent to the oceans) and traverse inward. Then find cells that can reach both oceans.
BFS Approach
Use BFS to find all cells that can reach each ocean. Start BFS from the borders of the matrix and work inward. Then find cells that can reach both oceans.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Initialize pacific and atlantic visited arrays
- Perform DFS from Pacific borders (left and top)
- Perform DFS from Atlantic borders (right and bottom)
- Find cells that appear in both pacific and atlantic visited arrays
- Return [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the matrix with different colors showing cells reachable from the Pacific, Atlantic, or both oceans.
Key visualization elements:
- Pacific reachable
- Atlantic reachable
- Both oceans reachable
Implementation Notes
This problem tests understanding of matrix traversal and is a good example of using DFS/BFS from the edges inward rather than traditional traversal.