Longest Increasing Path in a Matrix
You're given an m x n integer matrix. From any cell you can move up, down, left, or right, but never diagonally and never outside the matrix. Return the length of the longest path whose values strictly increase at every step, counted in cells.
Examples
matrix = [[7,8,9],[6,1,2],[5,4,3]] returns 9
Starting at the center 1, the path spirals outward through 2, 3, 4, 5, 6, 7, 8, and 9, visiting every cell.
matrix = [[1,1],[1,1]] returns 1
Equal neighbors don't count as increasing, so every path is a single cell.
matrix = [[2,9,4]] returns 2
Both 2 to 9 and 4 to 9 have length 2, and nothing continues past 9.
Constraints
- 1 <= m, n <= 200
- 0 <= matrix[i][j] <= 2^31 - 1
Hints
Because every step must strictly increase, can a path ever come back to a cell it visited? What does that make the graph of moves?
The moves form a directed acyclic graph, so the longest path can be found with memoized DFS or with a topological sort.
Give each cell an out-degree equal to its number of strictly larger neighbors. BFS in layers from the cells with out-degree 0, decrementing the out-degree of each smaller neighbor, and count the layers.
Drill This: Your Approach First
Approach
Treat every cell as a node with an edge to each strictly larger neighbor. The edges always point uphill, so the graph has no cycles and the answer is its longest path. Peel it in layers with a topological sort: count each cell's larger neighbors, queue the cells with none (local peaks), and repeatedly remove a whole layer, decrementing the counts of smaller neighbors and queuing any that drop to 0. The number of layers removed is the longest path. Memoized DFS, where each cell's answer is 1 plus the best of its larger neighbors, is equivalent but recurses up to m * n deep. O(m * n) time and space.
Time
O(m * n)
Space
O(m * n)
Pitfall
Solutions
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[][] out = new int[m][n];
Deque<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] > matrix[r][c]) out[r][c]++;
}
if (out[r][c] == 0) queue.add(new int[] {r, c});
}
}
int layers = 0;
while (!queue.isEmpty()) {
layers++;
for (int size = queue.size(); size > 0; size--) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && matrix[nr][nc] < matrix[r][c]) {
if (--out[nr][nc] == 0) queue.add(new int[] {nr, nc});
}
}
}
}
return layers;
}
}from collections import deque
class Solution:
def longestIncreasingPath(self, matrix) -> int:
m, n = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
out = [[0] * n for _ in range(m)]
queue = deque()
for r in range(m):
for c in range(n):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] > matrix[r][c]:
out[r][c] += 1
if out[r][c] == 0:
queue.append((r, c))
layers = 0
while queue:
layers += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and matrix[nr][nc] < matrix[r][c]:
out[nr][nc] -= 1
if out[nr][nc] == 0:
queue.append((nr, nc))
return layers