Longest Increasing Path in a Matrix
HardP3Coding
matrix is an m x n grid of integers. A path moves from a cell to an adjacent cell (up, down, left or right, no diagonals) and every step must go to a strictly larger value. Return the number of cells on the longest such path. A single cell is a path of length 1.
Example 1
- Input
- matrix = [[9,9,4],[6,6,8],[2,1,1]]
- Output
- 4
- Why
- The path 1 -> 2 -> 6 -> 9 has 4 cells.
Example 2
- Input
- matrix = [[3,4,5],[3,2,6],[2,2,1]]
- Output
- 4
- Why
- The path 3 -> 4 -> 5 -> 6 has 4 cells.
Example 3
- Input
- matrix = [[1]]
- Output
- 1
Constraints
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 10^9
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 10. ⌘Enter runs, ⌘⇧Enter submits.