Longest Increasing Path in a Matrix Hard 0 attempts
LeetCode ↗

Longest Increasing Path in a Matrix

Hard GraphBFSDFS LeetCode

Given an m x n integers matrix, return the length of the longest increasing path. From each cell, you can move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary. Each step must go to a cell with a strictly greater value.

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4 (path: 1 -> 2 -> 6 -> 9)

Example 2:

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

Approach: DFS + Memoization

For each cell, perform DFS to all 4 neighbors with strictly greater values. Cache the longest path from each cell to avoid recomputation. The answer is the maximum cached value.

function longestIncreasingPathInAMatrix(matrix) {
  const m = matrix.length, n = matrix[0].length;
  const memo = Array.from({length: m}, () => Array(n).fill(0));
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];
  function dfs(r, c) {
    if (memo[r][c]) return memo[r][c];
    let best = 1;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])
        best = Math.max(best, 1 + dfs(nr, nc));
    }
    return memo[r][c] = best;
  }
  let result = 0;
  for (let i = 0; i < m; i++)
    for (let j = 0; j < n; j++)
      result = Math.max(result, dfs(i, j));
  return result;
}

Time Complexity: O(m × n)

Space Complexity: O(m × n)

Saved in this browser only. Private to you.

JavaScript