⚡Flashcard Drill➔
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

  1. Model the matrix as a DAG with an edge from each cell to every strictly larger neighbour.
  2. dfs(i, j) returns the longest increasing path starting at (i, j), equal to 1 + max over larger neighbours.
  3. Memoise each cell's result, since many paths share suffixes.
  4. The answer is the maximum dfs over 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.
🎯 Drill This Card Now➔

🧩 Related 2-D Dynamic Programming Problems