Longest Increasing Path in a Matrix
You are given a grid of integers matrix with m rows and n columns. From any cell you may step to one of its four side neighbours (up, down, left or right); diagonal moves and moves off the grid are not allowed.
A path is increasing if every step lands on a cell whose value is strictly greater than the value of the cell you came from. Return the number of cells on the longest increasing path anywhere in the grid. A single cell on its own counts as a path of length 1.
Example 1
Example 2
Example 3
Constraints
1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
Pattern Path · Dynamic Programming · problem 160 of 169
Start simple
Run a plain DFS from every cell, trying all increasing continuations without remembering results: exponential time in the worst case (a grid like matrix[r][c] = r + c has exponentially many increasing paths).
The key idea
Draw an arrow from every cell to each side neighbour with a strictly larger value. Following arrows always increases the value, so you can never return to a cell: the arrows form a directed acyclic graph, and the task is the longest path in a DAG. That is a dynamic programme: best(cell) = 1 + max(best(next)) over its larger neighbours, and each cell's value only needs computing once.
A memoised DFS implements this directly. The reference solution instead uses an iterative topological peel, which avoids deep recursion on long paths. Count, for each cell, how many larger neighbours it has. Cells with zero are local maxima: their longest path is 1, so they form layer 1. Remove them and decrement the counters of their smaller neighbours; any cell whose counter drops to zero now has all of its larger neighbours resolved, so its longest path is exactly one more than the current layer. Repeat.
Layer k holds precisely the cells whose longest increasing path has k cells, so the number of layers is the answer. Each cell enters a layer once and each of its four edges is examined a constant number of times.
Complexity
- Time:
O(m · n) - Space:
O(m · n)
Python
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
rows, cols = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
def neighbours(r, c):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols:
yield nr, nc
# Edges go from a cell to each strictly larger neighbour.
# bigger[r][c] = how many larger neighbours (outgoing edges) a cell has.
bigger = [[0] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
for nr, nc in neighbours(r, c):
if matrix[nr][nc] > matrix[r][c]:
bigger[r][c] += 1
# Peel the graph layer by layer, starting from the local maxima.
# Cells in layer k start a longest increasing path of exactly k cells.
layer = [(r, c) for r in range(rows) for c in range(cols) if bigger[r][c] == 0]
length = 0
while layer:
length += 1
next_layer = []
for r, c in layer:
for nr, nc in neighbours(r, c):
if matrix[nr][nc] < matrix[r][c]:
bigger[nr][nc] -= 1
if bigger[nr][nc] == 0: # all its larger neighbours are peeled
next_layer.append((nr, nc))
layer = next_layer
return lengthJavaScript
var longestIncreasingPath = function(matrix) {
const rows = matrix.length, cols = matrix[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const neighbours = (r, c) => {
const result = [];
for (const [dr, dc] of dirs) {
const nr = r + dr, nc = c + dc;
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) result.push([nr, nc]);
}
return result;
};
// Edges go from a cell to each strictly larger neighbour.
// bigger[r][c] = how many larger neighbours (outgoing edges) a cell has.
const bigger = matrix.map(row => row.map(() => 0));
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
for (const [nr, nc] of neighbours(r, c)) {
if (matrix[nr][nc] > matrix[r][c]) bigger[r][c]++;
}
}
}
// Peel the graph layer by layer, starting from the local maxima.
// Cells in layer k start a longest increasing path of exactly k cells.
let layer = [];
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) if (bigger[r][c] === 0) layer.push([r, c]);
}
let length = 0;
while (layer.length) {
length++;
const nextLayer = [];
for (const [r, c] of layer) {
for (const [nr, nc] of neighbours(r, c)) {
if (matrix[nr][nc] < matrix[r][c] && --bigger[nr][nc] === 0) {
nextLayer.push([nr, nc]); // all its larger neighbours are peeled
}
}
}
layer = nextLayer;
}
return length;
};What the interviewer is checking
This checks whether you spot that a strict ordering makes the grid a DAG, which turns an exponential search into a DP with memoisation or topological order, and whether you think about recursion depth.
Mistakes to avoid
- Allowing equal neighbours, which breaks the strictly increasing rule and can create cycles.
- Keeping a "visited" set per DFS without memoising results, which is still exponential.
- Recursing on a long winding path in Python without raising the recursion limit (or using an iterative method).
- Assuming the longest path starts at the global minimum.
Follow-ups to expect
- Return the path itself, not just its length. (Store the best next cell per cell.)
- What if diagonal moves are allowed? (Same DP with eight neighbours.)
- What if the path only needs to be non-decreasing? (Equal cells form components; contract them first.)
In real software
Longest-path computations on DAGs drive critical-path scheduling in build systems and project planners, and terrain tools use the same idea to trace the longest uphill or downhill flow on an elevation grid.