Longest Increasing Path in a Matrix

Examples

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

The path 1 -> 2 -> 6 -> 9 (bottom row up to top-left) has length 4, and nothing longer exists.

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4

The path 3 -> 4 -> 5 -> 6 has length 4.

Constraints

• 1 <= rows, cols <= 200

• 0 <= matrix[i][j] <= 2^31 - 1

Approach

Define dp[r][c] as: "the length of the longest strictly increasing path that starts at cell (r, c)." That value is 1 (just the cell itself) plus the best dp value among its neighbors that hold a larger number — or just 1 if no neighbor is larger.

This is naturally a depth-first search from each cell, but the same cell gets visited over and over as the starting point of many different searches. Since strictly-increasing paths can't loop back on themselves, dp[r][c] never depends on itself, so it's safe to cache each cell's answer the first time it's computed and reuse it instantly every other time it's needed — turning an exponential search into one pass over every cell.

Solutions

Brute Force — DFS Without Memoization

From every cell, depth-first search outward through strictly larger neighbors, tracking the longest chain found. Correct, but the same cell can be re-explored from scratch many, many times as part of different searches.

function longestIncreasingPath(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function dfs(r, c) {
    let best = 1;
    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]) {
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }
    return best;
  }

  let answer = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      answer = Math.max(answer, dfs(r, c));
    }
  }
  return answer;
}

Time: Exponential in the worst case — the same cells get re-explored repeatedly · Space: O(rows * cols) — worst-case recursion depth

Optimal — DFS with a 2D Memo Table

Same depth-first search, but cache each cell's answer in a table the first time it's computed. Every later request for that cell returns instantly instead of re-searching.

function longestIncreasingPath(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const cache = Array.from({ length: rows }, () => new Array(cols).fill(0));
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function dfs(r, c) {
    if (cache[r][c] !== 0) return cache[r][c];

    let best = 1;
    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]) {
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }

    cache[r][c] = best;
    return best;
  }

  let answer = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      answer = Math.max(answer, dfs(r, c));
    }
  }
  return answer;
}

Time: O(rows * cols) · Space: O(rows * cols) — for the cache and the recursion stack