LeetCode · #329
Longest Increasing Path in a Matrix Solution
Given an integer matrix, return the length of the longest strictly increasing path using 4-directional moves.
01
Section One · Problem
Problem Statement
From each cell, you may move up, down, left, or right to a strictly larger value. Since values must strictly increase, the directed graph of allowed moves has no cycle. That makes the grid an implicit DAG.
Example
Input: [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
// One longest path is 1 → 2 → 6 → 9
02
Section Two · Approach 1
Plain DFS from Every Cell — Exponential Rework
A direct idea is to start DFS from every cell and recursively try every increasing neighbor. This is correct, but the same subpaths get recomputed again and again from overlapping starts.
Why it works
Strict increase prevents cycles, so every DFS branch eventually ends. The maximum path length over all starts is the answer.
Problem: Cells like a large local peak may be reached from many different starts, causing repeated recomputation. We need a way to process each directed edge once. Since the graph is a DAG, topological layering does exactly that.
03
Section Three · Approach 2
Topological BFS on the Implicit DAG — O(m · n)
Direct every edge from a smaller cell to a larger neighbor. Then compute inDegree[r][c] = number of smaller neighbors pointing into that cell. All local minima have indegree 0, so they form layer 1. Remove one layer at a time; the number of layers is the longest increasing path length.
💡 Mental model: Imagine water flowing uphill, but only one height level at a time. Cells with no smaller incoming neighbor are the lowest starting points. Once you finish a level, you expose the next level of cells whose remaining smaller predecessors have all been accounted for. The number of layers crossed is the path length.
- For every cell, inspect 4 neighbors.
- If a neighbor is smaller, it contributes 1 to the current cell's indegree.
- Seed a queue with all cells of indegree 0.
- BFS by levels; when processing a cell, decrement indegree of every larger neighbor.
- Each completed BFS level adds 1 to the longest path length.
Equivalent optimal idea:
- DFS + memoization is also O(m · n).
- This page uses topological BFS because it matches the graph concept-page framing: a longest path in a DAG can be read off from its layers.
04
Section Four · Trace
Visual Walkthrough
Trace the matrix [[9,9,4],[6,6,8],[2,1,1]].
Longest Increasing Path — topological layers
05
Section Five · Implementation
Code — Java & Python
Java — topological BFS on the grid DAG
import java.util.*;
class Solution {
private static final int[][] DIRS = {{1,0}, {-1,0}, {0,1}, {0,-1}};
public int longestIncreasingPath(int[][] matrix) {
int rows = matrix.length, cols = matrix[0].length;
int[][] indegree = new int[rows][cols];
Queue<int[]> queue = new ArrayDeque<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (matrix[nr][nc] < matrix[r][c]) indegree[r][c]++;
}
if (indegree[r][c] == 0) queue.offer(new int[] { r, c });
}
}
int length = 0;
while (!queue.isEmpty()) {
int size = queue.size();
length++;
for (int i = 0; i < size; i++) {
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 >= rows || nc < 0 || nc >= cols) continue;
if (matrix[nr][nc] <= matrix[r][c]) continue;
if (--indegree[nr][nc] == 0) queue.offer(new int[] { nr, nc });
}
}
}
return length;
}
}
Python — indegree layering
from collections import deque
class Solution:
def longestIncreasingPath(self, matrix: list[list[int]]) -> int:
rows, cols = len(matrix), len(matrix[0])
indegree = [[0] * cols for _ in range(rows)]
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
queue = deque()
for r in range(rows):
for c in range(cols):
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
indegree[r][c] += 1
if indegree[r][c] == 0:
queue.append((r, c))
length = 0
while queue:
length += 1
for _ in range(len(queue)):
r, c = queue.popleft()
for dr, dc in dirs:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
indegree[nr][nc] -= 1
if indegree[nr][nc] == 0:
queue.append((nr, nc))
return length
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Plain DFS from every cell | Can blow up exponentially | O(m · n) recursion in the worst case | Correct, but repeats the same suffix paths many times. |
| Topo BFS ← optimal | O(m · n) | O(m · n) | Each cell and edge is processed a constant number of times. |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Expected behavior | Why it matters |
|---|---|---|
| Single cell | Return 1 | The cell itself is a path of length 1. |
| All equal values | Return 1 | No strictly increasing move exists. |
| Strictly increasing row | Return row length | Each next cell forms the next topological layer. |
| Counting nodes vs edges | Return number of cells in the path | Layer count already matches cell count, starting at 1. |
| Using non-strict comparison | Wrong graph | Moves require strictly increasing values, not ≥. |
⚠ Common Mistake: Building edges in the wrong direction. For topological layering, we direct edges from smaller values to larger ones. Then local minima have indegree 0 and start the BFS. If you reverse the edges, the layer interpretation flips and your count becomes wrong unless you redesign the logic consistently.