Pacific Atlantic Water Flow
Medium
Array
Depth-First Search
Breadth-First Search
Matrix
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. 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)`. Water can only flow in four directions: up, down, left, and right from a cell to another with height equal or lower. Return *a list of grid coordinates* `[r, c]` *where water can flow to both the Pacific and Atlantic ocean*.
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]]
Example 2
Input: heights = [[1]]
Output: [[0,0]]
Example 3
Input: heights = [[2,1],[1,2]]
Output: [[0,0],[0,1],[1,0],[1,1]]

Constraints

  • m == heights.length
  • n == heights[r].length
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 10⁵
Time Complexity
O(m*n)
Space Complexity
O(m*n)
14
Case 1
Input: [[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]]
Expected: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Case 2
Input: [[1]]
Expected: [[0,0]]
Case 3
Input: [[2,1],[1,2]]
Expected: [[0,0],[0,1],[1,0],[1,1]]