Pacific Atlantic Water Flow
You are given an m x n matrix of heights representing an island. The Pacific Ocean touches the left and top edges, and the Atlantic Ocean touches the right and bottom edges. Water can flow from a cell to its neighboring cell in four directions (up, down, left, right) if the neighboring cell's height is less than or equal to the current cell's height. Return all grid coordinates where water can flow to both the Pacific and Atlantic Oceans.
Understand the problem
You are given an m x n matrix of heights representing an island. The Pacific Ocean touches the left and top edges, and the Atlantic Ocean touches the right and bottom edges. Water can flow from a cell to its neighboring cell in four directions (up, down, left, right) if the neighboring cell's height is less than or equal to the current cell's height. Return all grid coordinates where water can flow to both the Pacific and Atlantic Oceans.
Input: heights = [[1,2,2],[3,2,3],[2,4,5]]
Output: [[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
Pacific Ocean is reachable from all nine cells in this example. Atlantic Ocean is reachable from every cell except [0,0]. Therefore, the eight coordinates reachable from both oceans are returned.
Input: heights = [[1]]
Output: [[0,0]]
The only cell touches both the Pacific and Atlantic boundaries, so it can reach both oceans.
Constraints
- m == heights.length
- n == heights[r].length
- 1 <= m, n <= 200
- 0 <= heights[r][c] <= 100000
- Water flows only in four directions: up, down, left and right.
- Water can flow to a neighboring cell only if its height is less than or equal to the current cell's height.
- The answer can be returned in any order.
If water can only move downhill or stay at the same height, how can we find all cells that can reach both oceans without running DFS from every cell?