Longest Increasing Path in a Matrix
Visa● HardFULLTIMEONSITE INTERVIEWProblem statement
Given an integer matrix, return the maximum number of cells in a strictly increasing path.
From a cell you may move up, down, left, or right. Diagonal moves and wrap-around moves are not allowed. A cell may appear at most once in a path.
Function
longestIncreasingPath(matrix: int[][]) → intExamples
Example 1
matrix = [[9,9,4],[6,6,8],[2,1,1]]return = 4One longest path is 1 to 2 to 6 to 9.
Example 2
matrix = [[3,4,5],[3,2,6],[2,2,1]]return = 4The path 3,4,5,6 has length four.
Example 3
matrix = [[]]return = 0A matrix with no cells has no path.
Constraints
0 <= rows, columns <= 200.- Every row has the same length.
- Cell values fit in a signed 32-bit integer.