noodleProblems/
Longest Increasing Path in a Matrix
#148

Longest Increasing Path in a Matrix

AlgorithmhardArrayDynamic ProgrammingDepth First SearchBreadth First SearchGraphMemoizationMatrix

Given an m x n integer matrix, return the length of the **longest strictly increasing path**.

From a cell you may move in four directions — up, down, left, or right — to a neighbouring cell whose value is **strictly greater** than the current cell's. You may not move diagonally or step outside the grid, and the path length is counted as the number of cells visited.

The path may start and end at any cell.

Example cases

  • snaking path of length 4
    in matrix =
    994
    668
    211
    out 4
    The path 1 -> 2 -> 6 -> 9 increases by one step at a time for a length of 4.
  • diagonal moves not allowed
    in matrix =
    345
    326
    221
    out 4
    3 -> 4 -> 5 -> 6 is the longest; you cannot cut across diagonally.
  • single cell
    in matrix =
    1
    out 1

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1
Saved
matrix =
[[9,9,4],[6,6,8],[2,1,1]]