Watch 10 video solutions for Longest Increasing Path in a Matrix, a hard level problem involving Array, Dynamic Programming, Depth-First Search. This walkthrough by NeetCode has 88,814 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an m x n integers matrix, return the length of the longest 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).
Example 1:
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
Input: matrix = [[3,4,5],[3,2,6],[2,2,1]]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
Example 3:
Input: matrix = [[1]] Output: 1
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1Problem Overview: Given an m x n matrix, return the length of the longest strictly increasing path. From any cell you can move up, down, left, or right, but only to a cell with a larger value. The goal is to explore the grid efficiently without recomputing paths starting from the same cell.
Approach 1: Depth‑First Search (DFS) with Memoization (O(m*n) time, O(m*n) space)
Treat each cell as the start of a path and run DFS to explore neighbors with strictly larger values. The key insight: many paths overlap. If you already computed the longest path starting from a cell, reuse that result instead of recomputing it. Store results in a memo matrix where memo[r][c] represents the longest path beginning at that cell. Each cell is processed once, and every DFS only explores four directions. This converts an exponential search into linear work over all cells. This approach combines Depth‑First Search with Dynamic Programming via caching.
Approach 2: Topological Sort / BFS on Directed Graph (O(m*n) time, O(m*n) space)
Interpret the matrix as a directed graph. Create edges from smaller values to larger neighbors. Because values must increase, the graph is a DAG. Compute the outdegree for each cell (how many neighbors are larger). Cells with outdegree 0 represent path endpoints. Push them into a queue and perform level‑order processing similar to Kahn's algorithm. Each BFS layer represents one step backward in increasing paths. Reduce neighbor outdegrees as nodes are removed. The number of BFS layers processed equals the longest increasing path length. This reframes the grid as a graph problem with matrix traversal.
Recommended for interviews: DFS with memoization is the most commonly expected solution. It demonstrates understanding of DFS, caching overlapping subproblems, and converting exponential recursion into O(m*n) dynamic programming. Mentioning the topological sort interpretation shows deeper graph insight and can impress interviewers when discussing alternative formulations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS with Memoization | O(m*n) | O(m*n) | Best general solution. Clean recursion with caching avoids recomputation. |
| Topological Sort (BFS / Kahn's Algorithm) | O(m*n) | O(m*n) | Useful when modeling the matrix as a DAG and processing nodes by levels. |
| Naive DFS without Memoization | O((m*n)*4^(m*n)) worst case | O(m*n) | Conceptual baseline. Demonstrates the overlapping subproblem issue. |