Shortest Increasing Path to a Target
Uber● MediumFULLTIMEONSITE INTERVIEWProblem statement
Start at the top-left cell of grid. You may move up, down, left, or right only to a cell whose value is strictly greater than the current cell's value.
Return a shortest path ending at any cell whose value equals target. Encode a cell as row * columnCount + column. If multiple shortest paths exist, return the lexicographically smallest encoded path. Return an empty array if the target is unreachable.
Function
shortestIncreasingPath(grid: int[][], target: int) → int[]Examples
Example 1
grid = [[1,2,9],[4,5,3],[7,6,8]]target = 5return = [0,1,4]Paths [0,1,4] and [0,3,4] both use two moves. The first is lexicographically smaller.
Example 2
grid = [[5,4],[3,6]]target = 6return = []Neither neighbor of the starting value 5 is greater, so no move is possible.
Constraints
1 <= grid.length, grid[i].length <= 300.- Every row has the same length.
- Every value and
targetfits a signed 32-bit integer.