Highest Cells That Can Flow to Every Target
Google● HardNEW GRADONSITE INTERVIEWProblem statement
An integer grid gives the elevation of every cell. Water may move from a cell to an orthogonally adjacent cell whose elevation is less than or equal to the current elevation.
Given one or more target coordinates, find every cell from which water can reach every target. Among those cells, keep only the cells with the greatest elevation.
Return their coordinates sorted by row and then column. Return an empty array when no cell can reach every target. Duplicate target coordinates have no additional effect.
Function
highestCommonFlowCells(heights: int[][], targets: int[][]) → int[][]Examples
Example 1
heights = [[5,4,3],[6,1,2],[7,6,1]]targets = [[0,2],[2,2]]return = [[2,0]]Cell [2,0] has elevation 7 and has non-increasing routes to both targets.
Example 2
heights = [[3,3],[3,3]]targets = [[0,0],[1,1]]return = [[0,0],[0,1],[1,0],[1,1]]Every cell can reach both targets and all share the maximum feasible elevation.
Example 3
heights = [[1,2,1]]targets = [[0,0],[0,2]]return = [[0,1]]The middle cell flows downhill to either endpoint and is the unique highest feasible cell.
Constraints
1 <= rows, columns <= 200.-10^9 <= heights[r][c] <= 10^9.1 <= targets.length <= 20.- Every target is a valid grid coordinate.