Facebook PixelPacific Atlantic Water Flow — Coding Practice
Pacific Atlantic Water FlowMedium

Pacific Atlantic Water Flow

Medium 8.7k56% acceptance
GraphDepth-First SearchBreadth-First SearchMatrix

You are given an m × n integer grid heights representing terrain elevations. The Pacific Ocean touches the grid’s top and left edges; the Atlantic Ocean touches the bottom and right edges.

Water flows from a cell to a neighboring cell (up/down/left/right) only if the neighbor’s height is less than or equal to the current cell’s height. Water at any edge cell can flow directly into the ocean that edge borders.

Return every cell [r, c] from which water can reach both oceans.

Output ordering (required): return the coordinates sorted ascending by row, then by column.

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]]
These cells can drain toward both the top/left (Pacific) and bottom/right (Atlantic) edges, listed in row-major order.
Example 2
Input: heights = [[1]]
Output: [[0,0]]
A single cell touches every edge, so it reaches both oceans.
Constraints
  • m == heights.length, n == heights[0].length
  • 1 ≤ m, n ≤ 200
  • 0 ≤ heights[r][c] ≤ 100000
Asked atGoogleAmazonMetaApple
JavaScript
Loading editor…
Case 1
[[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
[[1]]
expected: [[0,0]]
Case 3
[[2,1],[1,2]]
expected: [[0,0],[0,1],[1,0],[1,1]]
Case 4
[[1,2,3],[8,9,4],[7,6,5]]
expected: [[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]
Case 5
[[3,3,3],[3,1,3],[3,3,3]]
expected: [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]
Case 6
[[10,10,10],[10,1,10],[10,10,10]]
expected: [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]