Given an m × n integer matrix, return the length of the longest strictly increasing path in it.
From each cell you can move up, down, left or right, but not diagonally or outside the matrix.
Examples
Example 1
- Input
- matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
- Output
- 4
- Why
- The longest increasing path is 1 → 2 → 6 → 9.
Example 2
- Input
- matrix = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]
- Output
- 4
- Why
- The longest increasing path is 3 → 4 → 5 → 6.
Example 3
- Input
- matrix = [[1]]
- Output
- 1
Constraints
1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1