Longest Increasing Path in a Matrix — Hard Problem & Solution

Return the length of the longest strictly increasing path in a matrix.

Difficulty: Hard
Topics: Arrays, Dynamic Programming, Matrix, Depth-First Search, Topological Sort
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Return the length of the longest strictly increasing path in a matrix. From a cell you may move up, down, left or right — never diagonally and never off the grid.

Example 1

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The path `1 → 2 → 6 → 9`.

Example 2

Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The path `3 → 4 → 5 → 6`; diagonal moves are not allowed.

Example 3

Input: matrix = [[1]]
Output: 1

Constraints

m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1

How to solve Longest Increasing Path in a Matrix

The strict increase makes the cell graph a DAG, so the longest path is well defined. Peel it like a topological sort: repeatedly strip the cells that have no larger neighbour left, counting the rounds.

Approach

For each cell count outdeg, its number of strictly larger neighbours.
Seed a queue with every cell of out-degree 0 — the possible path ends.
Each round, remove the whole current layer and decrement the out-degree of every strictly smaller neighbour, enqueuing those that reach 0.
The number of rounds is the answer.

Why it works

A cell can only be peeled once every cell it could step to has been peeled, so its round number is exactly one more than the longest path leaving it. The number of rounds is therefore the length of the longest path in the whole grid. This is also why the peel is iterative: a memoised DFS is equally correct but can recurse 40 000 deep on a 200 × 200 spiral.

Complexity

Time — O(m · n)
Space — O(m · n)

Pitfalls

Equal neighbours are not edges — the increase is strict — so plateaus never connect.
Recomputing the path from every cell without memoising is exponential.
The answer counts cells, so a 1 × 1 matrix answers 1, not 0.

Reference solution

Python

from typing import List
from collections import deque

def longestIncreasingPath(matrix: List[List[int]]) -> int:
    m, n = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    outdeg = [[0] * n for _ in range(m)]
    for i in range(m):
        for j in range(n):
            for di, dj in dirs:
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] > matrix[i][j]:
                    outdeg[i][j] += 1
    q = deque((i, j) for i in range(m) for j in range(n) if outdeg[i][j] == 0)
    length = 0
    while q:
        length += 1
        for _ in range(len(q)):
            r, c = q.popleft()
            for di, dj in dirs:
                nr, nc = r + di, c + dj
                if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] < matrix[r][c]:
                    outdeg[nr][nc] -= 1
                    if outdeg[nr][nc] == 0:
                        q.append((nr, nc))
    return length

JavaScript

var longestIncreasingPath = function(matrix) {
    var m = matrix.length, n = matrix[0].length, i, j, d;
    var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
    var outdeg = [];
    for (i = 0; i < m; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(0);
        outdeg.push(row);
    }
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            for (d = 0; d < 4; d++) {
                var ni = i + dr[d], nj = j + dc[d];
                if (ni < 0 || ni >= m || nj < 0 || nj >= n) continue;
                if (matrix[ni][nj] > matrix[i][j]) outdeg[i][j]++;
            }
        }
    }
    var q = [];
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) if (outdeg[i][j] === 0) q.push(i * n + j);
    }
    var len = 0;
    while (q.length > 0) {
        len++;
        var nq = [];
        for (var k = 0; k < q.length; k++) {
            var r = Math.floor(q[k] / n), c = q[k] % n;
            for (d = 0; d < 4; d++) {
                var nr = r + dr[d], nc = c + dc[d];
                if (nr < 0 || nr >= m || nc < 0 || nc >= n) continue;
                if (matrix[nr][nc] >= matrix[r][c]) continue;
                outdeg[nr][nc]--;
                if (outdeg[nr][nc] === 0) nq.push(nr * n + nc);
            }
        }
        q = nq;
    }
    return len;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue