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.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Depth-First Search, Matrix, Topological Sort
- Asked at: Amazon, Google, Flipkart, Nutanix, Epic Systems
- 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.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
Hints for Longest Increasing Path in a Matrix
Hint 1
Draw an edge from each cell to its strictly larger neighbours. Because values strictly increase, this graph has no cycles.
Hint 2
So the answer is the longest path in a DAG — memoise, or peel the graph layer by layer.
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
- 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 lengthJava
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