Longest Increasing Path in a Matrix
Problem statement
Return the number of cells in the longest strictly increasing path in matrix. A path may start at any cell. Each move goes one cell up, down, left, or right, and the next value must be strictly larger. Diagonal moves and wrapping across an edge are not allowed.
For this exercise, the matrix is nonempty and rectangular. Equal values cannot be consecutive on the path.
Function
longestIncreasingPath(matrix: int[][]) → intExamples
Example 1
matrix = [[9,9,4],[6,6,8],[2,1,1]]return = 4One longest path visits (2,1), (2,0), (1,0), and (0,0), with values 1, 2, 6, and 9. No increasing path contains more than four cells.
Example 2
matrix = [[3,4,5],[3,2,6],[2,2,1]]return = 4The path (1,1) to (0,1) to (0,2) to (1,2) has values 2, 4, 5, and 6. Its four cells form a longest path.
Example 3
matrix = [[1]]return = 1The only cell is a path of length 1.
Constraints
- 1 <= matrix.length <= 100
- 1 <= matrix[i].length <= 100
- 0 <= matrix[i][j] <= 10^9
- All rows have the same length.