4.24.7 — Longest Increasing Path in a Matrix

LeetCode 329 · Hard

The problem

Find the length of the longest path in a matrix where every step moves to an adjacent cell with a strictly larger value. You may move up, down, left or right, and you may not move diagonally or wrap around.

[[9,9,4],
 [6,6,8],
 [2,1,1]]      →  4     (1 → 2 → 6 → 9)

The pattern

This is DP, but the fill order is not obvious. In a normal grid DP you fill top to bottom; here a path can go in any direction, so there is no row or column ordering that guarantees the cells you need are ready.

That is exactly when memoised recursion wins. Write the recursion and let it discover the order:

\text{longest}(r, c) = 1 + \max\big(\text{longest}(nr, nc)\ :\ \text{neighbour is strictly larger}\big)

and 1 if no neighbour is larger.

No visited set is needed, and no undo. Because every step must strictly increase, a path can never return to a cell it has already used — the values would have to decrease. The strict increase makes the graph acyclic, and that is what makes memoisation valid at all.

Say that out loud: the "strictly increasing" condition means this is a DAG, so each cell's answer is a fixed number and can be cached. Without it, the answer would depend on the path taken to get there and no cache would be sound.

The solution

Python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        rows, cols = len(matrix), len(matrix[0])
        memo = {}

        def longest(r: int, c: int) -> int:
            if (r, c) in memo:
                return memo[(r, c)]

            best = 1                                   # the cell alone
            for nr, nc in ((r+1,c), (r-1,c), (r,c+1), (r,c-1)):
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + longest(nr, nc))

            memo[(r, c)] = best
            return best

        return max(longest(r, c) for r in range(rows) for c in range(cols))

TypeScript

function longestIncreasingPath(matrix: number[][]): number {
  if (!matrix.length) return 0;
  const rows = matrix.length, cols = matrix[0].length;
  const memo = Array.from({ length: rows }, () => new Array(cols).fill(0));

  function longest(r: number, c: number): number {
    if (memo[r][c]) return memo[r][c];

    let best = 1;
    for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]] as [number,number][]) {
      if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
        best = Math.max(best, 1 + longest(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, longest(r, c));

  return answer;
}

memo[r][c] starting at 0 doubles as "not computed", because every real answer is at least 1. That is a neat use of a value that cannot occur.

best starts at 1, since the cell itself is a path of length one.

Try every starting cell, because the longest path can begin anywhere — and thanks to the cache, later starts mostly hit precomputed answers.

No visited marking anywhere, and no restore. Compare 4.18.6 Word Search, which needs both because its paths can revisit cells in principle. Here the strict increase does the job for free, and knowing why is the difference between copying this solution and understanding it.

Complexity

O(rows \times cols) time. Each cell is computed once, and each computation looks at four neighbours — a constant.

O(rows \times cols) space for the cache and the recursion depth.

Without memoisation it is exponential, because the same cell is recomputed once per path reaching it.

The topological-sort alternative

There is a bottom-up version worth knowing, and it makes the DAG explicit.

Treat each cell as a node with an edge to every strictly larger neighbour. Compute each cell's outdegree — how many larger neighbours it has — and start from the cells with outdegree 0, which are the local maxima and can only end a path.

Then peel layer by layer, exactly like Kahn's algorithm in 4.20.9. The number of layers is the answer.

O(rows \times cols), iterative, no recursion depth risk. On a 200×200 grid the memoised version can be 40,000 frames deep, which is a genuine reason to prefer this one.

Mention it; write the memoised version. It is shorter and easier to explain.

Where this goes next

• Word Search — grid DFS that does need backtracking, because its paths have no monotonic constraint. The contrast is the lesson. 4.18.6.
• Longest Increasing Subsequence — the 1-D version, and it has an O(n \log n) trick that has no grid equivalent. 4.23.11.
• Course Schedule II — the topological peeling above. 4.20.9.
• Cherry Pickup, Minimum Falling Path Sum — grid DPs where the fill order is obvious, for contrast.

The rule: memoised recursion is the right form when the dependency order is hard to see. Bottom-up tabulation requires you to work the order out yourself; top-down discovers it. That is the point of having both forms in 4.22.

What the interviewer will push on

"Why is no visited set needed?" Strictly increasing values make cycles impossible.

"Why is memoisation valid?" The answer for a cell does not depend on how you arrived, because the graph is a DAG.

"Why top-down rather than bottom-up?" There is no obvious order to fill a table in; the recursion finds one.

"What is the complexity, and why is it not exponential?" Each cell is computed once. Without the cache it would be.

"What about stack depth?" Up to rows × cols frames. The topological version avoids it.

"Why start from every cell?" The longest path can begin anywhere, and the cache makes the repeated starts cheap.

One thing to volunteer: name the DAG. "Strictly increasing means the graph is acyclic, which is what makes the cache sound and the visited set unnecessary." That single sentence explains three of the design decisions at once.

Next: 4.24.8 Distinct Subsequences — back to the two-string grid, counting instead of measuring.