Longest Increasing Path in a Matrix
Find the longest strictly increasing path in a grid with DFS and memoisation: each cell's answer is 1 plus its best bigger neighbour, computed once.
Problem Understanding
Longest Increasing Path in a Matrix: given an m × n integer matrix, return the length of the longest strictly increasing path. From a cell you may move up, down, left or right, never diagonally or outside the grid.
Example: [[9,9,4],[6,6,8],[2,1,1]] returns 4, for the path 1 → 2 → 6 → 9.
The Intuition: Solve Each Cell Once
The best path starting at a cell is that cell plus the best path starting at one of its bigger neighbours. That gives a recursion:
dfs(r, c) = 1 + max(dfs(neighbour))over neighbours with a bigger value, or1if there are none.- The answer for a cell never depends on the route that reached it, so memoise it: the second call returns instantly.
- A strictly increasing path cannot revisit a cell, so there are no cycles and no visited set is needed.
Every cell is solved once and looks at four neighbours, so the whole grid costs O(m · n). This is depth-first search on a grid, as in Number of Islands, combined with the caching of dynamic programming.
Interactive Walkthrough
Each cell shows its value with its memo underneath once solved. The running call is solid and the calls waiting on the stack are tinted. Try Snake to watch one call chain run through every cell, then every later call hit the memo.
Dry Run Table
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]. Final memo, the longest path starting at each cell:
| col 0 | col 1 | col 2 | |
|---|---|---|---|
| row 0 | 9 → 1 | 9 → 1 | 4 → 2 |
| row 1 | 6 → 2 | 6 → 2 | 8 → 1 |
| row 2 | 2 → 3 | 1 → 4 | 1 → 2 |
memo(0, 2) = 2: 4 → 8.memo(2, 1) = 4: 1 → 2 (memo 3) → 6 (memo 2) → 9 (memo 1).
Answer: 4.
The Solution Template
Top-down DFS with a memo table. 0 in memo means not solved yet, since every real answer is at least 1.
Longest Increasing Path in a Matrix Code
1var longestIncreasingPath = function(matrix) {2 const m = matrix.length, n = matrix[0].length;3 const memo = Array.from({ length: m }, () => Array(n).fill(0));4 const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];5 const dfs = (r, c) => {6 if (memo[r][c]) return memo[r][c];7 let best = 1;8 for (const [dr, dc] of dirs) {9 const nr = r + dr, nc = c + dc;10 if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c])11 best = Math.max(best, 1 + dfs(nr, nc));12 }13 memo[r][c] = best;14 return best;15 };16 let ans = 0;17 for (let r = 0; r < m; r++)18 for (let c = 0; c < n; c++) ans = Math.max(ans, dfs(r, c));19 return ans;20};
Edge Cases & Common Mistakes
- Equal neighbours: the path must be strictly increasing;
>=would allow loops between equal cells. - No memo: plain DFS from every cell repeats the same sub-paths and is exponential on grids like the snake.
- Adding a visited set: unnecessary, and if it is shared across calls it wrongly blocks later paths.
- Single cell: the answer is 1.
- Very large grids: recursion depth can reach m · n on a snake-shaped matrix; the topological-sort version avoids that.
Summary
dfs(r, c) returns 1 plus the best dfs of any bigger neighbour, cached in memo. Strict increase rules out cycles, so no visited set is needed. Call it from every cell and return the maximum. O(m · n) time and space.
More practice: DSA interview questions with answers · patterns cheat sheet