329. Longest Increasing Path in a Matrix

Given an m×n integer matrix, return the length of the longest strictly increasing path, moving up, down, left or right.

Point an edge from each cell to every larger neighbor; the graph is a DAG. Repeatedly remove all cells with no smaller neighbors left (Kahn's algorithm). The number of layers peeled is the longest path.

1function longestIncreasingPath(matrix: number[][]): number {
2  const m = matrix.length, n = matrix[0].length, indeg = matrix.map((r) => r.map(() => 0));
3  const nbrs = (r: number, c: number) => [[r + 1, c], [r - 1, c], [r, c + 1], [r, c - 1]].filter(([x, y]) => x >= 0 && y >= 0 && x < m && y < n);
4  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++)
5    for (const [x, y] of nbrs(r, c)) if (matrix[x][y] < matrix[r][c]) indeg[r][c]++;
6  let layer = [];
7  for (let r = 0; r < m; r++) for (let c = 0; c < n; c++) if (!indeg[r][c]) layer.push([r, c]);
8  let depth = 0;
9  while (layer.length) {
10    depth++;
11    const next = [];
12    for (const [r, c] of layer)
13      for (const [x, y] of nbrs(r, c)) if (matrix[x][y] > matrix[r][c] && --indeg[x][y] === 0) next.push([x, y]);
14    layer = next;
15  }
16  return depth;
17}

depth = 0

matrix

9	9	4
6	6	8
2	1	1

smaller neighbors left

1	2	0
1	1	3
1	0	0

current layer

(0,2)

(2,1)

(2,2)

Count each cell's smaller neighbors. Cells with none are local minima.

1 / 0

Space: play/pause · ←/→: step