Longest Increasing Path in a Matrix

1. Define the problem

Longest Increasing Path in a Matrix

Given an m x n integer matrix, return the length of the longest path such that every step moves to a strictly greater value in a 4-directionally adjacent cell. Run depth-first search from every cell, only stepping to a neighbor with a larger value, and memoize the longest path starting at each cell so it is only ever computed once.

Constraints

m == matrix.length
n == matrix_i.length
1 ≤ m, n ≤ 200
0 ≤ matrix_i[j] ≤ 2³¹ - 1

Example

Inputmatrix = [[9,9,4],[6,6,8],[2,1,1]]

Output4

Explanation The longest increasing path is 1 → 2 → 6 → 9.

2. Know the words first

In plain terms

Memoize: Cache the result of a computation the first time it runs, so a repeated call with the same input can reuse the stored answer instead of recomputing it.

3. Visualize the solution

One cell per step of the longest path — four steps, left to right

6—

3—

0—

Statusdfs from (2,1) = 1

Try each strictly greater neighbor.

What happens in this step

dfs(index 7)  →  matrix[7] = 1  (row 2, col 1)

check neighbors in order: down (oob, skip)
                           up    → index 4 = 6, 6 > 1 → candidate (explored first, but its chain through 9 and 8 only reaches length 3)
                           right → index 8 = 1, 1 > 1 is false → skip
                           left  → index 6 = 2, 2 > 1 → candidate

Every strictly-greater neighbor gets its own dfs call; the best of all of them plus 1 becomes this cell's answer once they all return.

Step 1 of 5

Steps to visualize

The row has four slots, one for each step of the path the search walks. The label is the matrix cell, counted flat across the matrix (0-8); the value is the number stored there.
A slot shows — until the search has stepped onto that cell.
From a cell, try every neighbor with a strictly larger value.
A cell's longest path is 1 plus the best result among those neighbors, or just 1 if none qualify.
Cache that result the first time it is computed — a later call for the same cell returns instantly.
Run this from every cell and keep the largest result found.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

One cell per step of the longest path — four steps, left to right

6—

3—

0—

Statusdfs from (2,1) = 1

Try each strictly greater neighbor.

What happens in this step

dfs(index 7)  →  matrix[7] = 1  (row 2, col 1)

check neighbors in order: down (oob, skip)
                           up    → index 4 = 6, 6 > 1 → candidate (explored first, but its chain through 9 and 8 only reaches length 3)
                           right → index 8 = 1, 1 > 1 is false → skip
                           left  → index 6 = 2, 2 > 1 → candidate

Every strictly-greater neighbor gets its own dfs call; the best of all of them plus 1 becomes this cell's answer once they all return.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

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

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

    let best = 1;
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (matrix[nr][nc] <= matrix[r][c]) continue;

      best = Math.max(best, 1 + dfs(nr, nc));
    }

    memo[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)

6. Test cases

Test cases

Input	Expected	Covers
`matrix = [[9,9,4],[6,6,8],[2,1,1]]`	`4`	example from the docstring
`matrix = [[5]]`	`1`	smallest valid input, a single cell
`matrix = [[7,7],[7,7]]`	`1`	no strictly increasing move is possible anywhere
`matrix = [[1,2,3,4]]`	`4`	a single row that increases all the way across
`matrix = [[1],[2],[3]]`	`3`	a single column that increases all the way down
`matrix = [[3,4,5],[3,2,6],[2,2,1]]`	`4`	a second worked case with a path that bends through the grid
`matrix = [[1,2],[2,1]]`	`2`	a small grid where no path can exceed length 2

Longest Increasing Path in a Matrix