# Java recursive with memoization (17ms)

• ``````public class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
int[][] mem = new int[matrix.length][matrix[0].length];
int max = 0;
for (int i=0;i<matrix.length;i++)
for (int j=0;j<matrix[0].length;j++)
max = Math.max(max, findLongest(i,j,matrix, Integer.MIN_VALUE, 0, mem));
return max;
}
private int findLongest(int x, int y, int[][] matrix, int val, int count, int[][] mem){
if (x<0 || y<0 || x==matrix.length || y==matrix[0].length || matrix[x][y]<=val)
return count;

if (mem[x][y]>0) return mem[x][y]+count;

int max = findLongest(x+1, y, matrix, matrix[x][y], count+1, mem);
max = Math.max(max,findLongest(x-1, y, matrix, matrix[x][y], count+1, mem));
max = Math.max(max, findLongest(x, y+1, matrix, matrix[x][y], count+1, mem));
max = Math.max(max, findLongest(x, y-1, matrix, matrix[x][y], count+1, mem));

mem[x][y]=max-count;
return max;
}
}``````

• Was able to simplify after getting rid of redudant count variable

``````
public class Solution {
private static int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
public int longestIncreasingPath(int[][] matrix) {
if (matrix.length == 0) return 0;
int[][] mem = new int[matrix.length][matrix[0].length];
int max = 0;
for (int i=0;i<matrix.length;i++)
for (int j=0;j<matrix[0].length;j++)
max = Math.max(max, helper(i,j,matrix, -1, mem));
return max;
}
private int helper(int x, int y, int[][] mat, int oldVal, int[][] mem){
if (x<0||y<0||x==mat.length||y==mat[0].length||mat[x][y]<=oldVal) return 0;
if (mem[x][y]>0) return mem[x][y];
for (int[] dir : dirs)
mem[x][y]=Math.max(mem[x][y],helper(x+dir[0],y+dir[1],mat,mat[x][y],mem)+1);
return mem[x][y];
}
}
```
```

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