Given an m x n integer matrix, return the length of the longest strictly increasing path.
From a cell you may move in four directions — up, down, left, or right — to a neighbouring cell whose value is strictly greater than the current cell's. You may not move diagonally or step outside the grid, and the path length is counted as the number of cells visited.
The path may start and end at any cell.
Example
The path 1 -> 2 -> 6 -> 9 increases by one step at a time for a length of 4.
Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 2^31 - 1
Intuition
From each cell we want the longest strictly-increasing walk that starts there. The brute force does exactly that, literally: a plain DFS from every cell, exploring each strictly-larger neighbour and tracking the deepest chain — with no memory between starts.
function longestIncreasingPath(matrix) {
const rows = matrix.length, cols = matrix[0].length;
// Longest increasing path starting at (r, c), recomputed from scratch each call.
const dfs = (r, c) => {
let best = 1; // the cell alone is a path of length 1
for (const [nr, nc] of [[r+1,c],[r-1,c],[r,c+1],[r,c-1]]) {
if (nr<0||nc<0||nr>=rows||nc>=cols) continue;
if (matrix[nr][nc] > matrix[r][c]) // only step strictly upward
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;
}The waste: many cells funnel into the same upward chains, and each DFS re-derives those chains from scratch. Can we do better?
The key observation: because every step is strictly increasing, a path can never revisit a cell — the grid-with-upward-edges is a DAG, so longest(r, c) depends only on (r, c), never on how you arrived. That makes it a perfect memoisation target: cache each cell's answer the first time it's computed, and every later visit is an O(1) lookup. It's DFS plus a memo table — a DP over the implicit graph.
The walk is on the board, so the diagram is a gridWalkthrough. The cursor is the cell being solved; cells already memoised are marked. A badge-free board, so the captions carry the computed longest value. Walking it through:
DFS + memo — each cell's longest-path value is computed once, then reused
Start at the global minimum (2,1)=1. Its larger neighbours are (2,0)=2 and (1,1)=6 — recurse into them first.
From (2,0)=2 the only larger step is up to (1,0)=6, then (0,0)=9. longest(0,0)=1, longest(1,0)=2, longest(2,0)=3 — all memoised on the way back.
Back at (2,1)'s other branch: (1,1)=6 steps to (0,1)=9, giving longest(1,1)=2. Cells solved earlier (struck) are reused, not re-walked.
(2,1)=1 takes the better branch: 1 + longest(2,0)=3 gives a path 1→2→6→9 of length 4 — the answer.
The outer scan visits the rest, but each is an O(1) memo hit and none beats 4. Longest increasing path: 1 → 2 → 6 → 9.
Optimization
DFS with memoization
From any cell, the longest increasing path starting there depends only on its strictly-greater neighbours — and never on how you arrived (strictly increasing means a path can never revisit a cell, so there are no cycles to worry about). That makes the answer for each cell a fixed value we can cache.
Define longest(r, c) = the length of the longest increasing path that starts at (r, c): it is 1 plus the maximum longest over the four neighbours whose value is strictly larger (or just 1 if none qualify). Memoise each cell's result the first time it is computed. The overall answer is the maximum longest(r, c) across all cells.
O(m·n) time — with memoisation each cell's value is computed once and reused — and O(m·n) space for the memo table (plus recursion depth bounded by the longest path).
function longestIncreasingPath(matrix) {
const rows = matrix.length;
const cols = matrix[0].length;
// memo[r][c] = longest increasing path starting at (r, c); 0 means "not computed yet".
const memo = Array.from({ length: rows }, () => new Array(cols).fill(0));
const longest = (r, c) => {
if (memo[r][c] !== 0) return memo[r][c]; // reuse a solved cell
let best = 1; // the cell itself is a path of length 1
for (const [nr, nc] of [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]]) {
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
// Only step to a strictly larger neighbour.
if (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;
}Complexity analysis
Time complexity: O(m·n). Here's why:
- With memoisation, each cell's longest-path value is computed exactly once and cached.
- Computing one cell inspects its four neighbours — constant work — so the total is
4 · m·n.
Each of the m·n cells is solved once, giving O(m·n). Without the memo this would blow up exponentially as paths re-explore shared suffixes.
Space complexity: O(m·n). Here's why:
- The memo table is one entry per cell,
O(m·n). - The recursion stack is bounded by the longest increasing path, at most
O(m·n)deep (a snaking grid).
So the extra space is O(m·n).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| matrix = 42 | 1 | A single cell is a path of length 1. |
| matrix = 1234 | 4 | A strictly increasing row — the whole row is one path. |
| matrix = 4321 | 4 | Strictly decreasing reads as increasing right-to-left — still 4. |
| matrix = 77 77 | 1 | All equal — no strictly-increasing step exists, so every path is length 1. |
| matrix = 123 654 789 | 9 | A boustrophedon snake 1→2→…→9 winds through every cell — one path of length 9. |
Try it yourself
Write your solution against the real judge before checking the reference.