Skip to content
BASA DSA

Longest Increasing Path In a Matrix

Hard2-D Dynamic Programming

Return the greatest number of cells in a strictly increasing path through a matrix, moving orthogonally. Equal values cannot extend a path.

Example 1

0,09
0,19
0,24
1,06
1,16
1,28
2,02
2,11
2,21
Input grid. Cell values are shown at their original row and column; coordinates start at zero.
Input
matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output
4

Explanation

1->2->6->9 follows four orthogonal cells; equal values cannot extend it.

Example 2

0,05
0,15
Input grid. Cell values are shown at their original row and column; coordinates start at zero.
Input
matrix = [[5,5]]
Output
1

Explanation

Both cells equal 5, preventing strict movement between them.

Example 3

0,01
0,12
0,23
Input grid. Cell values are shown at their original row and column; coordinates start at zero.
Input
matrix = [[1,2,3]]
Output
3

Explanation

The row 1->2->3 forms a three-cell increasing path.

Constraints

  • 1 <= rows,columns <= 200
  • Values are nonnegative signed 32-bit integers

Function contractlongestIncreasingPathArguments: json
Loading draft…
SolutionRuns on your device