Description
Given an m x n matrix of non-negative integers representing the height of each unit cell, return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.
Examples
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]][[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]Pacific borders top/left edges; Atlantic borders bottom/right edges. Cell (0,4) with height 5 flows to Pacific via row 0 and to Atlantic via column 4. Cell (2,2) with height 5 is a local peak that can flow down to both oceans. Cell (3,0) with height 6 reaches Pacific directly (left edge) and Atlantic via path (3,0)→(3,1) with height 7→down to (4,0)→right along row 4.
heights = [[1]][[0,0]]A 1x1 grid has only cell (0,0). This cell touches both the Pacific (top and left borders) and Atlantic (bottom and right borders) simultaneously, so it can reach both oceans trivially.
heights = [[3,3,3],[3,1,3],[3,3,3]][[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]The center cell (1,1) has height 1, surrounded by cells of height 3. Water cannot flow uphill from height 1 to height 3, so (1,1) cannot reach any ocean. The 8 border cells all have height 3 and can flow along the border: corner (0,0) reaches Pacific via top/left edges and reaches Atlantic by flowing right to (0,2) then down to (2,2). All border cells are at equal height so water flows freely between them.
Constraints
- •
m == heights.length - •
n == heights[i].length - •
1 ≤ m, n ≤ 200