Longest Increasing Path in a Matrix
Given an m x n matrix of integers, return the length of the longest strictly increasing path.
A path starts at any cell and moves one step at a time up, down, left, or right. It may not leave the matrix, and it may not step onto a cell whose value is equal to or smaller than the current cell. Diagonal moves are not allowed. The length of a path is the number of cells it visits, so a single cell is a path of length 1.
Input & Output
Input
matrix — the grid of integers
Output
the number of cells on the longest strictly increasing path
Example
Input
matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
Output
4
Explanation
The path 1 -> 2 -> 6 -> 9 runs from the bottom row up the left side and visits four cells. No longer strictly increasing path exists.
Example
Input
matrix = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]
Output
4
Explanation
The path 3 -> 4 -> 5 -> 6 starts at the top-left and moves right, right, then down. The move from 5 to 6 is allowed, but no step onto an equal value such as the two 3s ever is.
Constraints
m == matrix.length,n == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1