Longest Increasing Path in a Matrix Hard 0 attempts
LeetCode ↗

Longest Increasing Path in a Matrix

Hard GraphBFSDFS LeetCode

Given an m x n matrix of integers, find the longest path you can trace where each step strictly increases in value. From any cell you may only step up, down, left, or right (no diagonal moves, and never off the edge of the grid), and every move must land on a cell whose value is strictly larger than the one you're leaving.

Return the number of cells in the path, including both endpoints.

Input Format
Implement longestIncreasingPathInAMatrix(matrix). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output
4

Example 2

Input
matrix = [[1]]
Output
1
Constraints
  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1
Test Cases (2)
Case 1
Args: [[[9,9,4],[6,6,8],[2,1,1]]] Expected: 4
Case 2
Args: [[[1]]] Expected: 1
Topics
GraphBFSDFS

Topological Layers

Orient edges from smaller cells to larger neighbors. Cells with no smaller neighbor start the first layer. Remove them, decrement successor indegrees, and repeat. The number of layers equals the longest increasing path; strict increases make the graph acyclic.

javascript
function longestIncreasingPathInAMatrix(matrix) {
  const rows=matrix.length,cols=matrix[0].length,dirs=[[1,0],[-1,0],[0,1],[0,-1]];
  const indegree=Array.from({length:rows},()=>Array(cols).fill(0)),queue=[];
  for(let r=0;r<rows;r++)for(let c=0;c<cols;c++){
    for(const [dr,dc] of dirs){const nr=r+dr,nc=c+dc;if(nr>=0&&nr<rows&&nc>=0&&nc<cols&&matrix[nr][nc]<matrix[r][c])indegree[r][c]++;}
    if(indegree[r][c]===0)queue.push([r,c]);
  }
  let head=0,length=0;
  while(head<queue.length){const end=queue.length;length++;
    while(head<end){const [r,c]=queue[head++];for(const [dr,dc] of dirs){const nr=r+dr,nc=c+dc;if(nr>=0&&nr<rows&&nc>=0&&nc<cols&&matrix[nr][nc]>matrix[r][c]&&--indegree[nr][nc]===0)queue.push([nr,nc]);}}
  }
  return length;
}

Time: O(rows × cols) | Space: O(rows × cols)

Saved in this browser only. Private to you.

JavaScript