Repository navigation
147 — Longest Increasing Path in a Matrix
LeetCode 329 · Hard. Given an m x n integers matrix, return the length of the longest increasing path in the 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).
Picture standing on a cell and asking "what's the longest hiking trail I can start here, only ever stepping to a strictly higher neighboring cell?" The answer only depends on the same question asked from each of your (up to four) higher neighbors — the longest trail from here is 1 + the best trail from whichever higher neighbor has the longest trail of its own. That's a DFS, but the huge win is that the "longest trail starting at cell (r, c)" never changes no matter which earlier cell asked about it — so instead of a bottom-up grid fill, this is DFS with a memo table keyed by cell coordinates, which fills in the same two-dimensional state space (row x column) that every 2-D DP problem in this category shares.
"Longest strictly-increasing path through a grid, moving in 4 directions" is the memoized-DFS-over-a-grid tell: the state is a cell (r, c), the answer at each cell depends only on the same answer at its higher-valued neighbors, and because the matrix has no cycles along an increasing path (values strictly increase, so you can never revisit a cell), a DFS with a memo table is guaranteed to terminate and never re-explore.
DFS outward from every cell, exploring every strictly-increasing path with no memoization — the same cell gets its "longest path from here" recomputed every time it's reached by a different starting point.
func longestIncreasingPathBruteForce(_ matrix: [[Int]]) -> Int {
guard !matrix.isEmpty, !matrix[0].isEmpty else { return 0 }
let rows = matrix.count
let cols = matrix[0].count
let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
func dfs(_ r: Int, _ c: Int) -> Int {
var best = 1
for (dr, dc) in directions {
let nr = r + dr, nc = c + dc
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c] {
best = max(best, 1 + dfs(nr, nc))
}
}
return best
}
var result = 0
for r in 0..<rows {
for c in 0..<cols {
result = max(result, dfs(r, c))
}
}
return result
}
// smoke test
print(longestIncreasingPathBruteForce([[9, 9, 4], [6, 6, 8], [2, 1, 1]])) // 4
print(longestIncreasingPathBruteForce([[3, 4, 5], [3, 2, 6], [2, 2, 1]])) // 4
print(longestIncreasingPathBruteForce([[1]])) // 1Big-O: exponential time in the worst case — without memoization, a cell reachable by many different increasing paths has its outgoing DFS re-run once per path that reaches it, and paths can overlap heavily in a grid with many equal-length increasing runs. O(rows · cols) space for the recursion stack in the worst case (one long snaking path).
Same DFS, but cache "the longest increasing path starting at this cell" the first time it's computed — since that answer never depends on how you arrived at the cell, only on its own value and its neighbors' values, it's safe to reuse forever after.
func longestIncreasingPath(_ matrix: [[Int]]) -> Int {
guard !matrix.isEmpty, !matrix[0].isEmpty else { return 0 }
let rows = matrix.count
let cols = matrix[0].count
let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
var memo = Array(repeating: Array(repeating: 0, count: cols), count: rows) // 0 = not yet computed
func dfs(_ r: Int, _ c: Int) -> Int {
if memo[r][c] != 0 { return memo[r][c] }
var best = 1
for (dr, dc) in directions {
let nr = r + dr, nc = c + dc
if nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c] {
best = max(best, 1 + dfs(nr, nc))
}
}
memo[r][c] = best
return best
}
var result = 0
for r in 0..<rows {
for c in 0..<cols {
result = max(result, dfs(r, c))
}
}
return result
}
// smoke test — same cases as the brute force
print(longestIncreasingPath([[9, 9, 4], [6, 6, 8], [2, 1, 1]])) // 4
print(longestIncreasingPath([[3, 4, 5], [3, 2, 6], [2, 2, 1]])) // 4
print(longestIncreasingPath([[1]])) // 1Big-O: O(rows · cols) time — each cell's DFS runs to completion exactly once (subsequent calls hit the memo), and each cell does O(1) work examining up to 4 neighbors. O(rows · cols) space for the memo table plus the recursion stack.
Both versions explore the exact same DFS branching — from each cell, try every neighbor with a strictly larger value — but the brute force treats every cell's "longest path from here" as needing to be recomputed each time some other path reaches it, so heavily-shared cells get their DFS subtree re-run many times over. The optimal version notices that a cell's answer depends only on its own coordinates (never on the path taken to reach it), so caching it in a memo[r][c] table the first time it's computed means every later reference is an O(1) lookup instead of a re-run. Turning "recompute per visit" into "compute once, cache by coordinate" is what turns exponential path exploration into a flat O(rows · cols) grid fill — it's a 2-D DP table, just populated top-down by DFS instead of bottom-up by nested loops.
-
Arrays and Strings — both
matrixandmemoare 2-D arrays under the hood, and every neighbor lookup is a plain array-index access guarded by bounds checks, the same array-access pattern underlying every grid problem in this batch. - Matrix Traversal — the state space is literally the grid, and the neighbor-checking with in-bounds guards is the same 4-directional traversal pattern used across every matrix problem.
- DFS and Backtracking — the core algorithm is DFS from each cell; the "optimal" version is exactly the brute-force DFS with one line added (a memo check) to skip re-exploring already-solved cells.
-
2D Dynamic Programming — the memo table is indexed by
(row, column), the same two-index state signature as every other problem in this category, just filled top-down via recursion rather than bottom-up via nested loops.
Longest Increasing Path is DFS with a memory — the longest increasing trail starting at a cell never depends on how you got there, so compute it once per cell and let every future visitor read it instead of re-walking it.
- Why is it safe to use
0as the "not yet computed" sentinel inmemo, given that every real answer (the longest path length starting at any cell) is at least1? - Why does this problem never need to worry about revisiting a cell within a single DFS call (no "visited" set is needed), unlike a typical graph DFS?
- Trace
dfsstarting from the cell holding1(bottom-middle) in[[9,9,4],[6,6,8],[2,1,1]]. Which path of increasing values does it discover, and what length does it cache for that cell?
⬅️ Previous: Interleaving String · Next: Distinct Subsequences ➡️