Given an m x n integers matrix, return the length of the longest increasing path. From each cell, you can move in 4 directions to adjacent cells with strictly greater values.
Input: [[9,9,4],[6,6,8],[2,1,1]] → Output: 4 (1→6→8→9)Input: [[3,4,5],[3,2,6],[2,2,1]] → Output: 4
DFS with memoization. memo[i][j] = longest increasing path starting at (i,j). For each cell, try 4 directions to cells with greater value.
- memo[i][j] stores the answer for each cell.
- dfs(i,j): if memo[i][j]>0 return it.
- Try 4 directions: if neighbor has greater value, recurse and take max.
- memo[i][j] = 1 + max over valid neighbors.
class Solution {
int[][] memo;
int m, n;
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int longestIncreasingPath(int[][] matrix) {
m=matrix.length; n=matrix[0].length; memo=new int[m][n]; int max=0;
for (int i=0;i<m;i++) for (int j=0;j<n;j++) max=Math.max(max,dfs(matrix,i,j));
return max;
}
private int dfs(int[][] mat, int r, int c) {
if (memo[r][c]>0) return memo[r][c];
memo[r][c]=1;
for (int[] d:dirs) {
int nr=r+d[0], nc=c+d[1];
if (nr>=0&&nr<m&&nc>=0&&nc<n&&mat[nr][nc]>mat[r][c])
memo[r][c]=Math.max(memo[r][c],1+dfs(mat,nr,nc));
}
return memo[r][c];
}
}
- Time Complexity: O(M*N)
- Space Complexity: O(M*N)