NeetCode #726LC-329Hard2-D Dynamic ProgrammingNC 150NC 250
← Back to All Problems#726 · #329 · Longest Increasing Path in a Matrix(矩阵中的最长递增路径)
📌 Problem Statement & Constraints
Given an
m x n integer matrix, return the length of the longest strictly increasing path, moving up, down, left, or right (no diagonals). Constraints: 1 <= m, n <= 200, 0 <= matrix[i][j] <= 2^31 - 1.💡 Core Algorithmic Approaches
- Model the matrix as a DAG with an edge from each cell to every strictly larger neighbour.
dfs(i, j)returns the longest increasing path starting at(i, j), equal to1 + maxover larger neighbours.- Memoise each cell's result, since many paths share suffixes.
- The answer is the maximum
dfsover all cells; no visited set is needed because strict increase prevents cycles.
💻 Benchmark Python3 Implementation
class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
memo = [[0] * n for _ in range(m)]
def dfs(i: int, j: int) -> int:
if memo[i][j]:
return memo[i][j]
best = 1
for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
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))
memo[i][j] = best
return best
return max(dfs(i, j) for i in range(m) for j in range(n))⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m * n): each cell is computed once and inspects four neighbours.
💾 Space Complexity
O(m * n) for the memo, plus recursion depth up to m * n.
⚠️ Interview Pitfalls & Follow-ups
- Using a visited set: it is unnecessary because strict increase guarantees acyclicity, and it would wrongly prune shared subpaths.
- Allowing equal neighbours: the path must be strictly increasing, so
>is required. - Omitting memoisation: the search blows up exponentially on a grid with many increasing routes.
- Ignoring recursion depth: for a 200x200 grid the depth can reach 40000, which may exceed the default limit; an iterative topological DP avoids it.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.