Longest Increasing Path in a Matrix
Longest Increasing Path in a Matrix is a hard graphs problem solved with the topological sort pattern.
The best approach, optimal (topological peeling), runs in O(m · n) time and O(m · n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (dfs from every cell) up.
Problem
You are given an m x n grid of integers matrix. From any cell you may step to one of its four neighbours (up, down, left or right), but only if the neighbour holds a strictly larger value.
Return the number of cells in the longest path you can walk this way. A path may start at any cell, and a single cell counts as a path of length 1.
Examples
Example 1
- Input
matrix = [[3,4,5],[2,9,6],[1,8,7]]- Output
9- Why
- Start at 1 and walk 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9, a spiral through every cell.
Example 2
- Input
matrix = [[5,5],[5,5]]- Output
1- Why
- Equal neighbours do not count as increasing, so every path is a single cell.
Example 3
- Input
matrix = [[1,10,2]]- Output
2- Why
- 1 → 10 or 2 → 10; you cannot continue past 10 because both of its neighbours are smaller.
Constraints
1 <= m, n <= 200wheremandnare the number of rows and columns.0 <= matrix[i][j] <= 2^31 - 1- Moves go up, down, left or right; no diagonals and no wrapping around the border.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (DFS from every cell) | O(4^(m·n)) worst case | O(m · n) |
| DFS with memoization | O(m · n) | O(m · n) |
| Optimal (topological peeling) | O(m · n) | O(m · n) |
1Brute force (DFS from every cell)
O(4^(m·n)) worst caseThe same suffix of a path is recomputed for every path that reaches it, which grows exponentially.O(m · n)Recursion depth can reach the length of the longest path.From every cell, run a DFS that tries every larger neighbour and returns 1 plus the best result among them. Nothing is cached, so the same cells are explored again and again.
- For each cell (i, j), compute dfs(i, j) and keep the maximum.
- dfs(i, j) = 1 + max(dfs(neighbour)) over neighbours with a strictly larger value, or 1 if there are none.
class Solution {
private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
public int longestIncreasingPath(int[][] matrix) {
int best = 0;
for (int i = 0; i < matrix.length; i++)
for (int j = 0; j < matrix[0].length; j++)
best = Math.max(best, dfs(matrix, i, j));
return best;
}
private int dfs(int[][] g, int r, int c) {
int best = 1;
for (int[] d : DIRS) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < g.length && y < g[0].length && g[x][y] > g[r][c])
best = Math.max(best, 1 + dfs(g, x, y));
}
return best;
}
}class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(r: int, c: int) -> int:
best = 1
for dr, dc in dirs:
x, y = r + dr, c + dc
if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[r][c]:
best = max(best, 1 + dfs(x, y))
return best
return max(dfs(i, j) for i in range(m) for j in range(n))class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int best = 0;
for (int i = 0; i < (int)matrix.size(); i++)
for (int j = 0; j < (int)matrix[0].size(); j++)
best = max(best, dfs(matrix, i, j));
return best;
}
private:
int dfs(vector<vector<int>>& g, int r, int c) {
static const int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int best = 1;
for (auto& d : dirs) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < (int)g.size() && y < (int)g[0].size() && g[x][y] > g[r][c])
best = max(best, 1 + dfs(g, x, y));
}
return best;
}
};function longestIncreasingPath(matrix) {
const m = matrix.length, n = matrix[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
function dfs(r, c) {
let best = 1;
for (const [dr, dc] of dirs) {
const x = r + dr, y = c + dc;
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[r][c])
best = Math.max(best, 1 + dfs(x, y));
}
return best;
}
let best = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
best = Math.max(best, dfs(i, j));
return best;
}2DFS with memoization
O(m · n)Each cell is computed once and looks at 4 neighbours.O(m · n)The memo table, plus recursion that can be as deep as the longest path.The longest path starting at a cell is the same no matter how you got there, so store it the first time you compute it. Every cell is then solved exactly once.
- memo[i][j] = 0 means not computed yet.
- dfs(i, j): if memo is set, return it; otherwise compute 1 + max over larger neighbours, store and return.
- Answer = max of dfs over all cells.
class Solution {
private static final int[][] DIRS = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
private int[][] memo;
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length, n = matrix[0].length, best = 0;
memo = new int[m][n];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
best = Math.max(best, dfs(matrix, i, j));
return best;
}
private int dfs(int[][] g, int r, int c) {
if (memo[r][c] != 0) return memo[r][c];
int best = 1;
for (int[] d : DIRS) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < g.length && y < g[0].length && g[x][y] > g[r][c])
best = Math.max(best, 1 + dfs(g, x, y));
}
return memo[r][c] = best;
}
}class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
memo = [[0] * n for _ in range(m)]
def dfs(r: int, c: int) -> int:
if memo[r][c]:
return memo[r][c]
best = 1
for dr, dc in dirs:
x, y = r + dr, c + dc
if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[r][c]:
best = max(best, 1 + dfs(x, y))
memo[r][c] = best
return best
return max(dfs(i, j) for i in range(m) for j in range(n))class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size(), best = 0;
memo.assign(m, vector<int>(n, 0));
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
best = max(best, dfs(matrix, i, j));
return best;
}
private:
vector<vector<int>> memo;
int dfs(vector<vector<int>>& g, int r, int c) {
static const int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
if (memo[r][c] != 0) return memo[r][c];
int best = 1;
for (auto& d : dirs) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < (int)g.size() && y < (int)g[0].size() && g[x][y] > g[r][c])
best = max(best, 1 + dfs(g, x, y));
}
return memo[r][c] = best;
}
};function longestIncreasingPath(matrix) {
const m = matrix.length, n = matrix[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const memo = Array.from({ length: m }, () => new Array(n).fill(0));
function dfs(r, c) {
if (memo[r][c] !== 0) return memo[r][c];
let best = 1;
for (const [dr, dc] of dirs) {
const x = r + dr, y = c + dc;
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[r][c])
best = Math.max(best, 1 + dfs(x, y));
}
memo[r][c] = best;
return best;
}
let best = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
best = Math.max(best, dfs(i, j));
return best;
}3Optimal (topological peeling)
O(m · n)Every cell enters the queue once and checks its 4 neighbours.O(m · n)The in-degree table and the queue.Treat each cell as a node with an edge to every strictly larger neighbour. The graph has no cycles. Count, for each cell, how many smaller neighbours point into it; cells with count 0 are local minimums and form the first layer. Remove a layer, lower the counts of the cells it points to, and the cells that drop to 0 form the next layer. The number of layers is the length of the longest path, and no recursion is needed.
- indeg[i][j] = number of neighbours with a smaller value.
- Put every cell with indeg 0 in a queue; layers = 0.
- While the queue is not empty: layers++, and for each cell in the current layer, decrement indeg of every larger neighbour, adding it to the queue when it reaches 0.
- Return layers.
class Solution {
public int longestIncreasingPath(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
int[][] indeg = new int[m][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] < matrix[i][j]) indeg[i][j]++;
}
if (indeg[i][j] == 0) q.add(new int[] { i, j });
}
int layers = 0;
while (!q.isEmpty()) {
layers++;
for (int size = q.size(); size > 0; size--) {
int[] c = q.poll();
for (int[] d : dirs) {
int x = c[0] + d[0], y = c[1] + d[1];
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[c[0]][c[1]]
&& --indeg[x][y] == 0)
q.add(new int[] { x, y });
}
}
}
return layers;
}
}class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
indeg = [[0] * n for _ in range(m)]
layer = []
for i in range(m):
for j in range(n):
for dr, dc in dirs:
x, y = i + dr, j + dc
if 0 <= x < m and 0 <= y < n and matrix[x][y] < matrix[i][j]:
indeg[i][j] += 1
if indeg[i][j] == 0:
layer.append((i, j))
layers = 0
while layer:
layers += 1
nxt = []
for r, c in layer:
for dr, dc in dirs:
x, y = r + dr, c + dc
if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[r][c]:
indeg[x][y] -= 1
if indeg[x][y] == 0:
nxt.append((x, y))
layer = nxt
return layersclass Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
vector<vector<int>> indeg(m, vector<int>(n, 0));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
for (auto& d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] < matrix[i][j]) indeg[i][j]++;
}
if (indeg[i][j] == 0) q.push({i, j});
}
int layers = 0;
while (!q.empty()) {
layers++;
for (int size = q.size(); size > 0; size--) {
auto [r, c] = q.front();
q.pop();
for (auto& d : dirs) {
int x = r + d[0], y = c + d[1];
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[r][c] && --indeg[x][y] == 0)
q.push({x, y});
}
}
}
return layers;
}
};function longestIncreasingPath(matrix) {
const m = matrix.length, n = matrix[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const indeg = Array.from({ length: m }, () => new Array(n).fill(0));
let layer = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) {
for (const [dr, dc] of dirs) {
const x = i + dr, y = j + dc;
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] < matrix[i][j]) indeg[i][j]++;
}
if (indeg[i][j] === 0) layer.push([i, j]);
}
let layers = 0;
while (layer.length > 0) {
layers++;
const next = [];
for (const [r, c] of layer) {
for (const [dr, dc] of dirs) {
const x = r + dr, y = c + dc;
if (x >= 0 && y >= 0 && x < m && y < n && matrix[x][y] > matrix[r][c] && --indeg[x][y] === 0)
next.push([x, y]);
}
}
layer = next;
}
return layers;
}Edge cases to test
- A single cell (answer 1)
- All values equal (answer 1)
- A snake-shaped path that visits every cell
- A single row or a single column
Hints
Hint 1
A strictly increasing path can never return to a cell it already used, so there are no cycles to worry about.
Hint 2
The longest path starting at a cell depends only on that cell, not on how you reached it. Can you cache it?
Hint 3
Alternatively, think of each cell as a node with an edge to every larger neighbour: the answer is the number of layers when you peel the graph from its sinks (or sources) like a topological sort.
FAQ
What is the best time complexity for Longest Increasing Path in a Matrix?
Optimal (topological peeling) runs in O(m · n) time and O(m · n) extra space. Every cell enters the queue once and checks its 4 neighbours.
Which pattern does Longest Increasing Path in a Matrix use?
It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.
Is there a brute force solution for Longest Increasing Path in a Matrix?
Yes. Brute force (DFS from every cell) takes O(4^(m·n)) worst case time and O(m · n) space. From every cell, run a DFS that tries every larger neighbour and returns 1 plus the best result among them.
Which edge cases should I test for Longest Increasing Path in a Matrix?
A single cell (answer 1); All values equal (answer 1); A snake-shaped path that visits every cell; A single row or a single column.