# Longest Increasing Path in a Matrix

• the time complexity of the second solution should be O(mn) in total, isn't it?

• can you give more examples of questions where onion peeling is used for solving the question?

• class Solution {
public int longestIncreasingPath(int[][] matrix) {

``````    if(matrix.length == 0 || matrix[0].length==0){
return 0;
}

int [][] maxpath = new int [matrix.length][matrix[0].length];

for(int i = 0; i < matrix.length; i++){
for(int j = 0; j< matrix[0].length; j++)
maxpath[i][j] = -1;

}

for(int i = 0; i < matrix.length; i++){
for(int j = 0; j< matrix[0].length; j++)
findMax(matrix, maxpath, i, j);
}

int max = -1;

for(int i = 0; i < matrix.length; i++){
for(int j = 0; j< matrix[0].length; j++)
if(maxpath[i][j]> max){
max = maxpath[i][j];
}
}

return max;

}

public void findMax(int[][] matrix, int[][] maxpath, int i, int j){

if(maxpath[i][j] != -1){
return;
}

int[][] adj = {{0, -1}, {-1, 0}, {0, 1}, {1,0}};
int result = -1;
for(int k = 0; k < 4; k++){

if(newx >= 0 && newx < matrix.length && newy >= 0 && newy< matrix[0].length){
if(matrix[newx][newy]> matrix[i][j]){
findMax(matrix, maxpath, newx, newy);
if( maxpath[newx][newy] + 1 > result)
result = maxpath[newx][newy] + 1;
}
}

}

if(result == -1){
maxpath[i][j] = 1;
}else{
maxpath[i][j] = result;
}

}
``````

}

• Why you add zero as boundaries in the Peeling Onion method, I think it is not necessary

• Who can help explain why the Time complexity of Approach 1 is O(2^(m+n))?
Thanks.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.