TL;DR
Memoized DFS over the grid where dp[i][j] = longest increasing path starting at (i, j) — O(m·n) time, O(m·n) space. Strict increase makes the cells a DAG, so a topological peel is the bottom-up equivalent.
Approach 1 — Brute force DFS
From each cell, recursively explore every strictly-larger neighbor and take the deepest chain, with no caching.
from typing import List
def longestIncreasingPath(matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
def dfs(i: int, j: int) -> int:
best = 1
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]:
best = max(best, 1 + dfs(ni, nj))
return best
return max(dfs(i, j) for i in range(m) for j in range(n))
Complexity: exponential in the worst case — the same cell is re-explored from many predecessors. Too slow for 40,000 cells.
Approach 2 — Memoized DFS (top-down DP)
The insight: the longest increasing path starting at (i, j) depends only on (i, j) — the route that arrived there is irrelevant. And because every step goes to a strictly larger value, the dependency graph is acyclic, so caching each cell’s result is safe and each is computed exactly once.
State / recurrence. dp[i][j] = length of the longest strictly-increasing path that starts at cell (i, j):
dp[i][j] = 1 + max(dp[ni][nj]) over neighbors (ni,nj) with matrix[ni][nj] > matrix[i][j]
= 1 if no larger neighbor exists
from typing import List
from functools import lru_cache
def longestIncreasingPath(matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
@lru_cache(maxsize=None)
def dfs(i: int, j: int) -> int:
best = 1
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]:
best = max(best, 1 + dfs(ni, nj))
return best
return max(dfs(i, j) for i in range(m) for j in range(n))
Walkthrough with matrix = [[9,9,4],[6,6,8],[2,1,1]]. The cell holding 1 (bottom middle) can step to a larger neighbor: 1 → 2 gives 2, 2 → 6 gives 3, 6 → 9 gives 4. So dfs at that 1 returns 4, the maximum over all cells. Cells like the top-left 9 have no larger neighbor and return 1.
Each step must go to a strictly larger value, so edges point one way and no cycle can form. That 1 reaches 6 both directly and through 2; the recurrence takes the deeper chain:
flowchart LR
A["1"] --> B["2"] --> C["6"] --> D["9"]
A --> C
Complexity: O(m·n) time (each cell computed once, O(1) neighbors), O(m·n) space for the cache and recursion.
Approach 3 — Topological peeling (bottom-up DP, Kahn’s algorithm)
The insight: direct each grid edge from the smaller cell to the larger one; this is a DAG. Kahn’s algorithm (repeatedly removing nodes with no outgoing edges) processes cells layer by layer — the number of layers is exactly the longest path length. Here “outdegree” counts strictly-larger neighbors; peaks (outdegree 0) form the first layer.
from typing import List
from collections import deque
def longestIncreasingPath(matrix: List[List[int]]) -> int:
if not matrix or not matrix[0]:
return 0
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
leaves = deque(
(i, j) for i in range(m) for j in range(n) if outdeg[i][j] == 0
)
length = 0
while leaves:
length += 1
for _ in range(len(leaves)):
i, j = leaves.popleft()
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[ni][nj] -= 1
if outdeg[ni][nj] == 0:
leaves.append((ni, nj))
return length
Complexity: O(m·n) time, O(m·n) space — the same asymptotics as memoized DFS, but iterative, so it avoids Python’s recursion-depth limit on large grids.
Common pitfalls
- Using
>= instead of strict > for the neighbor comparison — equal-valued neighbors are not part of an increasing path and would create cycles.
- Adding an explicit visited set: unnecessary and wrong here, since strict increase already forbids revisiting.
- Returning the count of edges instead of cells; the length is the number of cells, so a single cell answers
1, not 0.
- Forgetting the empty-matrix guard before reading
matrix[0].
Pattern takeaway
When a grid’s moves are constrained so no cycle can form (here, strictly increasing values), the cells become a DAG and “longest path” becomes a DP: cache each cell’s best onward path and reuse it. Top-down this is memoized DFS; bottom-up it is a topological peel (Kahn’s algorithm), where the number of peeling rounds equals the longest chain. Reach for this whenever a directed, acyclic dependency underlies a grid or graph.