Longest Increasing Path in a Matrix

Hard
920.

Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix is a hard coding problem on arrays, dynamic programming and depth-first search, asked in Amazon, Google, Flipkart and Nutanix interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} matrix
 * @return {number}
 */
var longestIncreasingPath = function(matrix) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Increasing Path in a Matrix — Problem & Solution

Longest Increasing Path in a Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Longest Increasing Path in a Matrix is a hard coding problem on arrays, dynamic programming and depth-first search, asked in Amazon, Google, Flipkart and Nutanix interviews.

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

Hints for Longest Increasing Path in a Matrix

  1. Hint 1

    Draw an edge from each cell to its strictly larger neighbours. Because values strictly increase, this graph has no cycles.

  2. Hint 2

    So the answer is the longest path in a DAG — memoise, or peel the graph layer by layer.

  3. Hint 3

    Cells with no larger neighbour are the path endpoints; start there and work backwards.

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

  1. For each cell count outdeg, its number of strictly larger neighbours.
  2. Seed a queue with every cell of out-degree 0 — the possible path ends.
  3. Each round, remove the whole current layer and decrement the out-degree of every strictly smaller neighbour, enqueuing those that reach 0.
  4. 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

Java

public static int longestIncreasingPath(int[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[] dr = { 1, -1, 0, 0 };
    int[] dc = { 0, 0, 1, -1 };
    int[][] outdeg = new int[m][n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int d = 0; d < 4; d++) {
                int 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]++;
            }
        }
    }
    int[] q = new int[m * n];
    int head = 0, tail = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) if (outdeg[i][j] == 0) q[tail++] = i * n + j;
    }
    int len = 0;
    while (head < tail) {
        len++;
        int end = tail;
        while (head < end) {
            int r = q[head] / n, c = q[head] % n;
            head++;
            for (int d = 0; d < 4; d++) {
                int 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;
                if (--outdeg[nr][nc] == 0) q[tail++] = nr * n + nc;
            }
        }
    }
    return len;
}

C++

int longestIncreasingPath(vector<vector<int>>& matrix) {
    int m = (int) matrix.size(), n = (int) matrix[0].size();
    int dr[4] = { 1, -1, 0, 0 };
    int dc[4] = { 0, 0, 1, -1 };
    vector<vector<int>> outdeg(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            for (int d = 0; d < 4; d++) {
                int 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]++;
            }
        }
    }
    vector<int> q;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) if (outdeg[i][j] == 0) q.push_back(i * n + j);
    }
    size_t head = 0;
    int len = 0;
    while (head < q.size()) {
        len++;
        size_t end = q.size();
        while (head < end) {
            int r = q[head] / n, c = q[head] % n;
            head++;
            for (int d = 0; d < 4; d++) {
                int 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;
                if (--outdeg[nr][nc] == 0) q.push_back(nr * n + nc);
            }
        }
    }
    return len;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming