Skip to main content

24. Longest Increasing Path in a Matrix

hardAsked at GitLab

Find the longest strictly increasing path in an integer matrix using 4-directional moves.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n matrix of integers, return the length of the longest strictly increasing path. You may move up, down, left, or right but not diagonally and not outside the grid.

Constraints

  • 1 <= m, n <= 200
  • 0 <= matrix[i][j] <= 2^31 - 1

Examples

Example 1

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

Example 2

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

Approaches

1. Plain DFS

DFS from every cell, taking the max neighbor extension. Exponential without memoization.

Time
exp
Space
O(m*n)
/* DFS without memo recomputes shared subpaths repeatedly. */

Tradeoff:

2. DFS with memoization (topological DP)

Memoize the longest path starting at each cell — the matrix is a DAG (edges only go to larger cells), so each cell is solved once. Return the max over all start cells.

Time
O(m*n)
Space
O(m*n)
function longestIncreasingPath(matrix){
  const m = matrix.length, n = matrix[0].length;
  const memo = Array.from({length:m}, () => new Array(n).fill(0));
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  const 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 && nc >= 0 && nr < m && nc < n && matrix[nr][nc] > matrix[r][c])
        best = Math.max(best, 1 + dfs(nr, nc));
    }
    return memo[r][c] = best;
  };
  let ans = 0;
  for (let r = 0; r < m; r++)
    for (let c = 0; c < n; c++)
      ans = Math.max(ans, dfs(r, c));
  return ans;
}

Tradeoff:

GitLab-specific tips

GitLab loves this one as a stand-in for the longest critical path through a CI graph — they will ask if you can adapt the memo into Kahn's-style scheduling once parallel runners enter the picture.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Longest Increasing Path in a Matrix and other GitLab interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →