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 - 1The key challenge in #329 Longest Increasing Path in a Matrix is finding the longest strictly increasing sequence of cells where movement is allowed in four directions. A brute-force exploration from every cell would repeatedly recompute paths, leading to exponential time.
An efficient strategy uses Depth-First Search (DFS) with memoization. Treat each cell as a node in a graph and explore its neighbors only if their value is greater. By storing previously computed results in a dp or memo table, each cell’s longest path is calculated once and reused in later computations. This significantly reduces redundant work.
Another perspective models the grid as a Directed Acyclic Graph (DAG), where edges point from smaller values to larger values. Using topological sorting with BFS (Kahn’s algorithm), you can process layers of nodes and determine the maximum path length.
Both approaches efficiently traverse the matrix while avoiding recomputation, resulting in near-linear complexity relative to the number of cells.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DFS with Memoization | O(m × n) | O(m × n) |
| Topological Sort (BFS on DAG) | O(m × n) | O(m × n) |
NeetCode
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.
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.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int longestIncreasingPath(vector<vector<int>>& matrix) {
7 if (matrix.empty() || matrix[0].empty()) return 0;
8 int m = matrix.size(), n = matrix[0].size();
9 vector<vector<int>> memo(m, vector<int>(n, -1));
10 int maxLen = 0;
11
12 std::function<int(int, int)> dfs = [&](int x, int y) {
13 if (memo[x][y] != -1) return memo[x][y];
14 vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
15 int max_len = 1;
16 for (const auto& d : directions) {
17 int nx = x + d.first, ny = y + d.second;
18 if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
19 max_len = max(max_len, 1 + dfs(nx, ny));
20 }
21 }
22 memo[x][y] = max_len;
23 return max_len;
24 };
25
26 for (int i = 0; i < m; ++i) {
27 for (int j = 0; j < n; ++j) {
28 maxLen = max(maxLen, dfs(i, j));
29 }
30 }
31 return maxLen;
32 }
33};In this C++ solution, we utilize a lambda function for the DFS which captures the variables by reference and uses the memoization technique to store results of previously computed paths. This approach efficiently calculates the longest increasing path starting from each cell and stores the result in the memo table to prevent redundant calculations.
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 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.
1public class Solution {
2 public int LongestIncreasingPath(int[][] matrix) {
3 if (matrix == null || matrix.Length == 0) return 0;
4 int m = matrix.Length, n = matrix[0].Length;
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) dp[i] = new int[n];
int maxLen = 0;
int dfs(int x, int y) {
if (dp[x][y] != 0) return dp[x][y];
int[][] directions = new int[][]{new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};
dp[x][y] = 1;
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
dp[x][y] = Math.Max(dp[x][y], 1 + dfs(nx, ny));
}
}
return dp[x][y];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxLen = Math.Max(maxLen, dfs(i, j));
}
}
return maxLen;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, it is a popular Hard-level interview problem because it combines graph traversal, dynamic programming, and matrix processing. Companies often expect candidates to recognize the DFS + memoization optimization.
The optimal approach is DFS with memoization. Each cell explores increasing neighbors while caching the longest path starting from that cell, preventing repeated computations and reducing the complexity to O(m × n).
Yes. By viewing the matrix as a DAG, you can compute out-degrees and apply BFS-based topological sorting (Kahn’s algorithm). Each layer in the BFS represents an increase in path length.
A matrix-based DP or memoization table combined with DFS recursion works best. The grid can also be treated as a directed graph where edges point from smaller values to larger ones.
This C# solution follows a similar logic by using dynamic programming principles. The DFS function explores potential paths from each cell, leveraging an array dp to store already calculated results and determine the longest increasing path starting from a specific point.