Longest Increasing Path in a Matrix
HardPrompt
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:
[1, 2, 6, 9]Example 2:
[3, 4, 5, 6]Example 3:
Input: matrix = [[1]]
Output: 1
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores every possible increasing path starting from every cell in the matrix. For each cell, it performs a Depth First Search (DFS) to find the longest path originating from it. The overall maximum length found among all starting cells is the answer.
Algorithm
- Initialize a global variable
maxLengthto 0. - Create a main function that iterates through every cell
(i, j)of the matrix. - For each cell, call a recursive DFS helper function,
dfs(row, col), to compute the length of the longest increasing path starting at that cell. - Update
maxLength = max(maxLength, result from dfs). - The
dfs(row, col)function works as follows: a. InitializemaxPathFromCellto 1 (for the cell itself). b. Explore the four adjacent neighbors (up, down, left, right). c. For each neighbor(nextRow, nextCol)that is within the matrix boundaries and has a valuematrix[nextRow][nextCol] > matrix[row][col], make a recursive call:1 + dfs(nextRow, nextCol). d. UpdatemaxPathFromCellwith the maximum length found among all valid neighbors. e. ReturnmaxPathFromCell. - After iterating through all cells, return
maxLength.
Walkthrough
We define a main function that iterates through every cell (i, j) of the matrix. For each cell, it calls a recursive DFS helper function, dfs(row, col), to compute the length of the longest increasing path starting at (row, col). The main function keeps track of the maximum length found so far and updates it after each DFS call.
The dfs(row, col) function explores the four adjacent neighbors (up, down, left, right). For each neighbor (nextRow, nextCol) that is within the matrix boundaries and has a value greater than matrix[row][col], it makes a recursive call. The length of the path starting from (row, col) is 1 + max(length of paths from valid neighbors). The base case for the recursion is a cell from which no further increasing path can be formed; in this case, the path length is 1 (the cell itself).
This method is straightforward but highly inefficient because it repeatedly calculates the longest path for the same cells multiple times. For example, the longest path from cell A might be needed to calculate the path from cell B, and also later for the path from cell C.
class Solution { private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private int m, n; public int longestIncreasingPath(int[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } m = matrix.length; n = matrix[0].length; int maxLength = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { maxLength = Math.max(maxLength, dfs(matrix, i, j)); } } return maxLength; } private int dfs(int[][] matrix, int row, int col) { int maxPath = 1; for (int[] dir : dirs) { int newRow = row + dir[0]; int newCol = col + dir[1]; if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] > matrix[row][col]) { maxPath = Math.max(maxPath, 1 + dfs(matrix, newRow, newCol)); } } return maxPath; }}Complexity
Time
O((m*n) * 4^(m*n)) - This is a loose upper bound, but the complexity is exponential. From each cell, the search can branch out, and the same subproblems (finding the longest path from a particular cell) are solved repeatedly. This leads to an exponential number of function calls.
Space
O(m * n) - The space is dominated by the recursion stack depth, which in the worst case (a path that visits every cell) can be the total number of cells in the matrix.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to a massive number of redundant computations.
Will result in a 'Time Limit Exceeded' (TLE) error for all but the smallest matrices.
This approach significantly optimizes the brute-force DFS by using memoization, a top-down dynamic programming technique. We use a cache (a 2D array) to store the length of the longest increasing path starting from each cell. This avoids recomputing the result for the same cell multiple times, drastically improving performance.
Algorithm
- Initialize a memoization cache
memo[m][n]with all values as 0. A value of 0 indicates the result for that cell has not been computed. - Initialize a global variable
maxLengthto 0. - Iterate through every cell
(i, j)of the matrix. - For each cell, call a recursive DFS helper function,
dfs(row, col, matrix, memo). - Update
maxLength = max(maxLength, result from dfs). - The
dfs(row, col, matrix, memo)function: a. Ifmemo[row][col]is not 0, it means we have already computed the result. Return the cached valuememo[row][col]immediately. b. Otherwise, initializemaxPathFromCellto 1. c. Explore the four adjacent neighbors. d. For each valid neighbor(nextRow, nextCol)with a greater value, recursively calldfs(nextRow, nextCol, matrix, memo)and updatemaxPathFromCell = max(maxPathFromCell, 1 + result). e. Before returning, store the computed result:memo[row][col] = maxPathFromCell. f. ReturnmaxPathFromCell. - After iterating through all cells, return
maxLength.
Walkthrough
The overall structure is similar to the brute-force approach: iterate through all cells and perform a DFS from each to find the longest path. The key difference is the addition of a memo cache, a 2D array of the same dimensions as the input matrix, initialized to 0. memo[i][j] will store the length of the longest increasing path starting at cell (i, j).
The modified dfs(row, col) function first checks if memo[row][col] is non-zero. If it is, it means we have already computed the result for this cell, so we can return the cached value immediately. If the result is not in the cache, we compute it just like in the brute-force approach: explore all valid neighbors, make recursive calls, and find the maximum path length. Before returning the computed length, we store it in memo[row][col] so it can be reused later.
By caching the results, we ensure that the DFS for each cell is computed exactly once. This transforms the exponential complexity of the brute-force approach into a linear one.
class Solution { private int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; private int m, n; public int longestIncreasingPath(int[][] matrix) { if (matrix == null || matrix.length == 0) { return 0; } m = matrix.length; n = matrix[0].length; int[][] memo = new int[m][n]; int maxLength = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { maxLength = Math.max(maxLength, dfs(matrix, i, j, memo)); } } return maxLength; } private int dfs(int[][] matrix, int row, int col, int[][] memo) { if (memo[row][col] != 0) { return memo[row][col]; } int maxPath = 1; for (int[] dir : dirs) { int newRow = row + dir[0]; int newCol = col + dir[1]; if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] > matrix[row][col]) { maxPath = Math.max(maxPath, 1 + dfs(matrix, newRow, newCol, memo)); } } memo[row][col] = maxPath; return maxPath; }}Complexity
Time
O(m * n) - Each cell's result is computed exactly once. The main loops iterate through all `m*n` cells. The `dfs` function for each cell `(i, j)` runs its main logic only once before its result is cached. During this run, it performs constant work (checking four neighbors). Therefore, the total time is proportional to the number of cells.
Space
O(m * n) - This space is used for the `memo` cache which stores the result for each cell, and for the recursion stack. The recursion depth can be up to `m*n` in the worst case.
Trade-offs
Pros
Highly efficient and optimal solution.
Guaranteed to pass within typical time limits by eliminating redundant computations.
It correctly identifies and solves the overlapping subproblems inherent in the problem.
Cons
Requires extra space for the memoization table.
The recursion stack can be deep for certain matrix configurations, though this is also true for the brute-force approach.
Solutions
Solution
class Solution {private int m;private int n;private int[][] matrix;private int[][] f;public int longestIncreasingPath(int[][] matrix) { m = matrix.length; n = matrix[0].length; f = new int[m][n]; this.matrix = matrix; int ans = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { ans = Math.max(ans, dfs(i, j)); } } return ans; }private int dfs(int i, int j) { if (f[i][j] != 0) { return f[i][j]; } int[] dirs = {-1, 0, 1, 0, -1}; for (int k = 0; k < 4; ++k) { int x = i + dirs[k]; int y = j + dirs[k + 1]; if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) { f[i][j] = Math.max(f[i][j], dfs(x, y)); } } return ++f[i][j]; }}class Solution { public: int longestIncreasingPath ( vector < vector < int >>& matrix ) { int m = matrix . size (), n = matrix [ 0 ]. size (); int f [ m ][ n ]; memset ( f , 0 , sizeof ( f )); int ans = 0 ; int dirs [ 5 ] = { - 1 , 0 , 1 , 0 , - 1 }; function < int ( int , int ) > dfs = [ & ]( int i , int j ) -> int { if ( f [ i ][ j ]) { return f [ i ][ j ]; } for ( int k = 0 ; k < 4 ; ++ k ) { int x = i + dirs [ k ], y = j + dirs [ k + 1 ]; if ( x >= 0 && x < m && y >= 0 && y < n && matrix [ x ][ y ] > matrix [ i ][ j ]) { f [ i ][ j ] = max ( f [ i ][ j ], dfs ( x , y )); } } return ++ f [ i ][ j ]; }; for ( int i = 0 ; i < m ; ++ i ) { for ( int j = 0 ; j < n ; ++ j ) { ans = max ( ans , dfs ( i , j )); } } return ans ; } };class Solution: def longestIncreasingPath(self, matrix: List[List[int]]) -> int: @ cache def dfs(i: int, j: int) -> int: ans = 0 for a, b in pairwise((- 1, 0, 1, 0, - 1)): x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and matrix[x][y] > matrix[i][j]: ans = max(ans, dfs(x, y)) return ans + 1 m, n = len(matrix), len(matrix[0]) return max(dfs(i, j) for i in range(m) for j in range(n))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.