329. Longest Increasing Path in a Matrix

The matrix is secretly a DAG — each cell points only to strictly-larger neighbors, so there are no cycles. DFS with per-cell memoization computes the longest path from every cell in O(m·n) total, visiting each cell at most twice.

● HardDFS + MemoizationDAG DPMatrix TraversalTypeScript

PROBLEM What we're solving

Given an m × n integer matrix, return the length of the longest strictly increasing path. From any cell you may move up, down, left, or right — never diagonally — and only to a strictly larger value. You cannot revisit cells.

Worked example:
[[9,9,4],[6,6,8],[2,1,1]] → 4
The path 1 → 2 → 6 → 9 (row 2 col 1 → row 2 col 0 → row 1 col 0 → row 0 col 0) has length 4.

KEY IDEA The matrix is a DAG — no cycle risk, so memoize freely

Insight → Because movement is restricted to strictly increasing values, you can never return to a cell you came from. The implicit graph is a Directed Acyclic Graph (DAG). That means DFS never loops, and memo[r][c] = longest increasing path starting at (r, c)can be computed once and reused. Each cell is computed exactly once — there are no "cycle guard" visited arrays needed.

RECIPE DFS + memo: 1 + max over strictly-greater neighbors

0 · Initialize memo. A Map (or 2D array) stores results for cells already computed. Without it, repeated DFS would cost O(m²·n²) in the worst case.
1 · DFS from (r, c). If the cell is in memo, return immediately. Otherwise, try all 4 neighbors. A neighbor (nr, nc) qualifies only if it is in bounds and matrix[nr][nc] > matrix[r][c]. Why strict? To form an increasing path — equal values would allow cycles.
2 · Recurrence. dp[r][c] = 1 + max(dp[nr][nc]) over valid neighbors. If no valid neighbor exists, the cell itself is a length-1 path.
3 · Memoize and return. Store the computed length so every future caller gets O(1) lookup.
4 · Outer loop. Call dfs(r, c) for every cell and track the global maximum. The answer is the largest value across all starting cells.

Classic confusion →People worry about needing a "visited" set to prevent cycles during DFS. You do not need one here. The strictly-increasing constraint is the cycle guard — if you're at value v, every reachable cell has value > v, so you can never revisit the current cell. Adding a visited set would break memoization and produce wrong answers on paths that share sub-paths.

COST Complexity & alternatives

Naive DFS (no memo)

O(m·n·4^(m·n))

Recomputes the same sub-paths exponentially.

DFS + Memoization

O(m·n)

Each cell computed once. O(m·n) space for memo + call stack.

Alternatives

Topological sort (Kahn's): Build the explicit DAG, compute in-degrees, BFS layer by layer. Same O(m·n) time, O(m·n) space, but more code. The memoized DFS is simpler and preferred in interviews.

Pattern transfer → The "DAG DP via DFS + memo" pattern applies to Number of Longest Increasing Subsequence, Unique Paths III (DAG with obstacles), Course Schedule (topo order), and any problem where the graph is implicitly acyclic due to a monotone constraint.

RUN IT DFS + memo — longest increasing path from each cell

matrix (rows separated by ;)

step 0 / 32

STARTMatrix loaded (3×3). Will DFS from every cell, memoizing results. The DAG structure (strictly increasing only) guarantees no cycles.

1▶function longestIncreasingPath(matrix: number[][]): number {
2▶  const rows = matrix.length;
3▶  const cols = matrix[0].length;
4▶  const memo = new Map<number, number>();
5 
6  function encode(r: number, c: number): number {
7    return r * cols + c;
8  }
9 
10  function dfs(r: number, c: number): number {
11    const key = encode(r, c);
12    if (memo.has(key)) return memo.get(key)!;
13 
14    const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
15    let best = 1;                              // cell itself counts
16    for (const [dr, dc] of dirs) {
17      const nr = r + dr;
18      const nc = c + dc;
19      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
20          && matrix[nr][nc] > matrix[r][c]) {  // strictly greater
21        best = Math.max(best, 1 + dfs(nr, nc));
22      }
23    }
24 
25    memo.set(key, best);
26    return best;
27  }
28 
29▶  let ans = 0;
30▶  for (let r = 0; r < rows; r++) {
31▶    for (let c = 0; c < cols; c++) {
32      ans = Math.max(ans, dfs(r, c));
33    }
34  }
35  return ans;
36}

State
ans: 0
Memo
???
???
???

current DFS cellmemoized (computed)chosen best neighbor

slowfast

TYPESCRIPT The solution, annotated

longestIncreasingPath.ts
function longestIncreasingPath(matrix: number[][]): number {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const memo = new Map<number, number>();

  function encode(r: number, c: number): number {
    return r * cols + c;
  }

  function dfs(r: number, c: number): number {
    const key = encode(r, c);
    if (memo.has(key)) return memo.get(key)!;

    const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
    let best = 1;                              // cell itself counts
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && matrix[nr][nc] > matrix[r][c]) {  // strictly greater
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }

    memo.set(key, best);
    return best;
  }

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

Reading it block by block

Lines 2–3 — dimensions. Cache rows and cols so every bounds check avoids re-accessing matrix.length.

Lines 4, 7–9 — memo + encode. A flat Map<number, number> stores results keyed by r * cols + c — the unique integer id of each cell. Using a flat key avoids allocating a 2D array.

Lines 11–12 — memo hit. If the cell is already computed, return immediately in O(1). This is the line that converts exponential DFS into linear total work.

Lines 14–20 — explore neighbors. For each of the 4 cardinal directions, move only when the neighbor is in-bounds and strictly greater. No visited set needed — the increasing constraint prevents any cycle. best starts at 1 because the cell itself counts as a path of length 1.

Lines 22–23 — memoize. Store best before returning so future callers skip the DFS entirely. Without this, the same sub-paths would be recomputed repeatedly.

Lines 26–31 — outer loop.Kick off a DFS from every cell and keep the running maximum. Any cell could be the start of the longest path, so we can't skip any.

Complexity → O(m·n) time: each cell is pushed onto the DFS call stack at most once, and when popped it does O(4) neighbor work before being memoized. Every subsequent call to that cell costs O(1). O(m·n) space for the memo map plus the implicit call stack, which is at most O(m·n) deep in the worst case (a single zigzag path through the entire matrix).

INTERVIEWFollow-ups they'll ask

"Can you do it iteratively?"Yes — build the explicit DAG, compute in-degrees, then run Kahn's BFS layer-by-layer. The answer is the number of BFS levels. Same asymptotic complexity, no recursion stack.
"What if the matrix has duplicates / non-strictly increasing?" Change > to >= — but then you need a real visited set per DFS call because cycles become possible.
"Return the actual path, not just its length?" Store a parent map alongside memo and reconstruct by following the chosen neighbor from the cell with the global maximum dp value.
"What if diagonal moves are allowed?" Expand the dirs array to 8 directions. The DAG property and memoization strategy remain unchanged.
"What about a 3D matrix?" Generalize dirs to 6 directions (±x, ±y, ±z) and encode with r * cols * depth + c * depth + d.

OPTIMAL DFS + Memoization

longestIncreasingPath.ts
function longestIncreasingPath(matrix: number[][]): number {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const memo = new Map<number, number>();

  function encode(r: number, c: number): number {
    return r * cols + c;
  }

  function dfs(r: number, c: number): number {
    const key = encode(r, c);
    if (memo.has(key)) return memo.get(key)!;

    const dirs: [number, number][] = [[-1,0],[1,0],[0,-1],[0,1]];
    let best = 1;                              // cell itself counts
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
          && matrix[nr][nc] > matrix[r][c]) {  // strictly greater
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }

    memo.set(key, best);
    return best;
  }

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

ALT 1 Topological-sort peeling (BFS by out-degree)

Time O(m·n) · Space O(m·n)

Treat each cell as a DAG node pointing to strictly-greater neighbors, then peel off the "sink" cells layer by layer — the number of layers is the longest path.

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

  // outDegree[r][c] = number of strictly-greater neighbors (edges OUT of this cell).
  const outDegree: number[][] = Array.from({ length: rows }, () =>
    new Array<number>(cols).fill(0),
  );

  // Cells with out-degree 0 are local peaks — the "sinks" of the DAG.
  const queue: [number, number][] = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (
          nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
          matrix[nr][nc] > matrix[r][c]
        ) {
          outDegree[r][c]++;
        }
      }
      if (outDegree[r][c] === 0) queue.push([r, c]);
    }
  }

  // Peel layer by layer. Each round removes the current peaks; a smaller
  // neighbor whose only-larger edge pointed here loses an out-edge and may
  // itself become a peak in the next round.
  let layers = 0;
  let frontier = queue;
  while (frontier.length > 0) {
    layers++;
    const next: [number, number][] = [];
    for (const [r, c] of frontier) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (
          nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
          matrix[nr][nc] < matrix[r][c]   // neighbor pointed UP to us
        ) {
          outDegree[nr][nc]--;
          if (outDegree[nr][nc] === 0) next.push([nr, nc]);
        }
      }
    }
    frontier = next;
  }

  return layers;
}

Note → This is Kahn's algorithm run on the reversed DAG: peaks (out-degree 0) are removed first, and a cell joins the next frontier once all of its strictly-greater neighbors have been peeled. No recursion stack — handy when the grid is large enough that a deep monotone path could overflow the call stack.

ALT 2 Plain DFS — no memoization

Time O(m·n·4^(m·n)) worst case · Space O(m·n) stack

The same recurrence as the optimal solution but with the memo table removed — correct, yet it recomputes shared sub-paths exponentially and TLEs on large grids.

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

  // No memo: every call re-explores the entire sub-DAG below (r, c).
  function dfs(r: number, c: number): number {
    let best = 1;                              // the cell itself
    for (const [dr, dc] of dirs) {
      const nr = r + dr;
      const nc = c + dc;
      if (
        nr >= 0 && nr < rows && nc >= 0 && nc < cols &&
        matrix[nr][nc] > matrix[r][c]          // strictly greater
      ) {
        best = Math.max(best, 1 + dfs(nr, nc));
      }
    }
    return best;
  }

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

Note → Included to show why the memo is essential. Because each cell's longest path is recomputed every time it is reached from a different start, the work explodes — a gradient grid where every cell flows into the next forces the same suffix to be re-walked over and over. Adding a single Map cache (the optimal solution) collapses this to O(m·n).

MNEMONIC The one-liner

"Strictly up only — the mountain climb never revisits, so memo each peak's altitude freely."

TRIGGERS When you see _ → reach for _

"longest path in a grid, only strictly greater"	DFS + per-cell memo (DAG DP)
matrix traversal, no revisit, monotone constraint	implicit DAG → no visited set needed
"starting from any cell"	outer loop calling dfs() on every cell, take max
path-length DP in a graph/grid	1 + max(dfs(neighbor)) recurrence

SKELETON The reusable shape

skeleton.ts
const memo = new Map<number, number>();
const encode = (r: number, c: number) => r * cols + c;

function dfs(r: number, c: number): number {
  const key = encode(r, c);
  if (memo.has(key)) return memo.get(key)!;
  let best = 1;
  for (const [dr, dc] of [[-1,0],[1,0],[0,-1],[0,1]]) {
    const nr = r + dr, nc = c + dc;
    if (inBounds && matrix[nr][nc] > matrix[r][c])
      best = Math.max(best, 1 + dfs(nr, nc));
  }
  memo.set(key, best);
  return best;
}
// outer loop: call dfs every cell, track max

FLASHCARDS Tap to flip

Why is no "visited" set needed in the DFS?

The strictly-increasing constraint is the cycle guard. You can only move to a larger value, so you can never revisit the current cell.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

What is the time complexity of the DFS + memoization solution?

QUESTION 02

Why is a "visited" array NOT needed during DFS for this problem?

QUESTION 03

Trace [[9,9,4],[6,6,8],[2,1,1]]. What is the longest increasing path length?

QUESTION 04

What does dp[r][c] represent in the memoization table?

QUESTION 05

If two adjacent cells have equal values (e.g., both are 6), can you move between them on an increasing path?

QUESTION 06

What is the space complexity of the memoized DFS?

QUESTION 07

Which alternative algorithm solves this problem iteratively in O(m·n)?

QUESTION 08

#329 · Longest Increasing Path in a MatrixDFS with memoization: the longest path through (r,c) is 1 plus the max over strictly greater neighbors. The DAG of increasing values guarantees no back-edges, making memoization safe.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA The matrix is a DAG — no cycle risk, so memoize freely

RECIPE DFS + memo: 1 + max over strictly-greater neighbors

COST Complexity & alternatives

Alternatives

RUN IT DFS + memo — longest increasing path from each cell

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL DFS + Memoization

ALT 1 Topological-sort peeling (BFS by out-degree)

ALT 2 Plain DFS — no memoization

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _