pacific-atlantic-water-flow.sh — zsh

Pacific Atlantic Water Flow

medium
graphmatrixdepth-first-searchbreadth-first-search

Water flows from a cell to equal-or-lower neighbors. Return all [row, column] cells that can reach both the Pacific (top/left) and Atlantic (bottom/right), in row-major order.

Constraints

  • 1 <= rows, columns <= 200
  • 0 <= heights[r][c] <= 100000

Follow-up

Why is reverse traversal from each ocean more efficient than searching from every cell?

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]]
Example 2
Input: heights = [[1]]
Output: [[0,0]]
Example 3
Input: heights = [[1,2]]
Output: [[0,0],[0,1]]
🔒 5 hidden
Running will execute all 8 cases, including 5 hidden ones.