# Java Solution: O(mn) Backtracking/DFS + DP: Accepted

• I am simply using Backtracking while storing the calculated values. I have added comments in the code. In case of any problem please add a comment.
The code can be written in fewer lines however that will reduce the readability and slows the debugging process.

``````public class Solution {

// There can be no repetetion of elements as the sequence must be strictly increasing.
// So we don't have to worry about loops. It will be handled implicitly.

int[][] solution;
int maxLength;
public int longestIncreasingPath(int[][] matrix) {
if(matrix==null || matrix.length==0){
return 0;
}
solution=new int[matrix.length][matrix[0].length];
maxLength=1; // default value

// Calculating the value for each cell.
int j;
for (int i = 0; i < matrix.length; i++) {
for (j = 0; j < matrix[0].length; j++) {
increasingSequence(matrix,i,j);
}
}
return maxLength;
}

public int increasingSequence(int[][] matrix, int i, int j){

// checking if already calculated, in case of already calculted value solution[i][j] will be > 0
if(solution[i][j]>0) {
return solution[i][j];
}
solution[i][j]=1;
// for the four sides we can go to
int one, two, three, four;
one=two=three=four=0;
if(matrix[max(i-1,0)][j]>matrix[i][j]) {
one = increasingSequence(matrix, max(i - 1, 0), j);
}
if(matrix[min(i + 1, matrix.length - 1)][j]>matrix[i][j]) {
two = increasingSequence(matrix, min(i + 1, matrix.length - 1), j);
}
if(matrix[i][max(j-1,0)]>matrix[i][j]) {
three = increasingSequence(matrix, i, max(j - 1, 0));
}
if(matrix[i][min(j+1,matrix[0].length-1)]>matrix[i][j]) {
four = increasingSequence(matrix, i, min(j + 1, matrix[0].length - 1));
}
// getting the max value among the four. Updating maxLength accordingly.
solution[i][j]=max(one,two,three,four)+1;
if(solution[i][j]>maxLength){
maxLength=solution[i][j];
}
return solution[i][j];
}

// basic util functions
public int max(int a, int b){
return a>=b?a:b;
}

public int max(int a, int b, int c, int d){
int temp1=c>=d?c:d;
return a>=b?a>=temp1?a:temp1:b>=temp1?b:temp1;
}

public int min(int a, int b){
return a<=b?a:b;
}
}
``````

In case of any improvements, no matter how small, please add a comment.