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.
This approach uses a combination of Depth First Search (DFS) and memoization to solve the problem efficiently. We explore each cell, attempting to find the longest increasing path starting from that cell. To avoid recalculating the path length for each call from the same cell, we use memoization to store already computed results.
In this Python solution, we define a helper function dfs that performs DFS on the matrix starting from a given cell. We utilize a memo table to store the longest path from each cell to avoid redundant calculations, improving performance significantly. The main function starts by iterating over each cell to compute the maximum length path by considering each cell as a starting point.
The time complexity is O(m * n) because each cell is computed once and cached. The space complexity is also O(m * n) due to the memoization table.
This approach systematically calculates the longest increasing path dynamically by first iterating over the matrix and then updating results based on previously computed values. By using a dynamic programming table, we determine, for each cell, the longest chain it can contribute to incrementally.
The JavaScript solution uses dynamic programming. For each cell, the function dfs recursively explores valid neighbors, resulting in the longest increasing path starting from that cell. The result for each cell is stored in a DP table before being returned, which ensures efficiency by preventing the recalculation of already known results.
JavaScript
C#
The time complexity is O(m * n) due to the fact that each matrix cell can be a starting point and is only calculated once with memoization guidance. The space complexity is O(m * n) because a result is stored for each cell in the DP table.
We design a function dfs(i, j), which represents the length of the longest increasing path that can be obtained starting from the coordinate (i, j) in the matrix. The answer is max_{i, j} dfs(i, j).
The execution logic of the function dfs(i, j) is as follows:
(i, j) has been visited, directly return f(i, j);(i, j), search the coordinates (x, y) in four directions. If 0 \le x < m, 0 \le y < n and matrix[x][y] > matrix[i][j], then search (x, y). After the search is over, update f(i, j) to f(i, j) = max(f(i, j), f(x, y) + 1). Finally, return f(i, j).The time complexity is O(m times n), and the space complexity is O(m times n). Where m and n are the number of rows and columns of the matrix, respectively.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Depth First Search (DFS) with Memoization | The time complexity is |
| Dynamic Programming | The time complexity is |
| Memoization Search | — |
| 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. |
Longest Increasing Path in a Matrix - Leetcode 329 • NeetCode • 88,814 views views
Watch 9 more video solutions →Practice Longest Increasing Path in a Matrix with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor