Longest Increasing Path in a Matrix medium
Description
Given an m × n integers matrix, return the length of the longest strictly increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Examples
> Case 1:
matrix = [[9, 9, 4], [6, 6, 8], [2, 1, 1]]
Output: 4
Explanation: longest path = [1, 2, 6, 9].
> Case 2:
matrix = [[3, 4, 5], [3, 2, 6], [2, 2, 1]]
Output: 4
Explanation: [3, 4, 5, 6].
> Case 3:
matrix = [[1]]
Output: 1Constraints
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 2^31 - 1
Why this is topo sort in disguise
Treat each cell as a graph node. Draw an edge (r, c) → (r', c') iff (r', c') is a 4-neighbor of (r, c) AND matrix[r'][c'] > matrix[r][c].
Because edges only go from smaller values to strictly larger values, the resulting graph is a DAG — no cycles possible (a cycle would require a value to be strictly larger than itself).
The problem becomes: find the longest path in this DAG. Two solutions:
Solution 1 — DFS with memoization (top-down)
For each cell, compute “longest increasing path starting here” by recursing into the strictly-larger 4-neighbors and adding 1. Cache results.
O(m × n) time and space — each cell is visited and computed once thanks to memoization.
Solution 2 — Kahn’s-based DP (bottom-up)
Build the DAG explicitly with indegrees, then process in topo order, propagating dp[cell] = max(dp[predecessor]) + 1. This is the “longest path on a DAG” DP from the applications page.
Same O(m × n) time. The “rounds” of Kahn’s correspond directly to path lengths.
Analysis
- Time:
O(m × n). - Space:
O(m × n).
Same skin
- Course Schedule II — different domain, same DAG.
- Parallel Courses — rounds-counting Kahn’s, same shape as the BFS variant here.
- Word Ladder — BFS shortest path, similar grid-on-graph framing.
- Longest Path in DAG (generic) — this is the canonical instance.
This is one of the rare problems where two completely different framings (DFS+memo and Kahn’s-DP) both reach the same O(m × n) answer. Recognizing that “every grid where you can only move to strictly-larger neighbors is a DAG” is the core skill.