# Easy Java Solution!

• ``````public class Solution {

public int longestIncreasingPath(int[][] matrix) {

if (matrix == null || matrix.length < 1 || matrix[0].length < 1)
return 0;

int max = 0, n = matrix.length, m = matrix[0].length;

// create a cache matrix
int[][] cache = new int[n][m];

// dfs search on every element in matrix
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
max = Math.max(dfs(matrix, Integer.MIN_VALUE, i, j, n, m, cache), max);
}
}
return max;
}

int dfs(int[][] matrix, int min, int i, int j, int n, int m, int[][] cache) {

// check boundary limits
if (i < 0 || j < 0 || i >= n || j >= m)
return 0;

// check min condition
if (matrix[i][j] <= min)
return 0;

// check into cache
if (cache[i][j] != 0)
return cache[i][j];

// update min
min = matrix[i][j];

// run dfs in all four directions
int a = dfs(matrix, min, i - 1, j, n, m, cache) + 1;
int b = dfs(matrix, min, i + 1, j, n, m, cache) + 1;
int c = dfs(matrix, min, i, j - 1, n, m, cache) + 1;
int d = dfs(matrix, min, i, j + 1, n, m, cache) + 1;

// find max and update cache
int max = Math.max(a, Math.max(b, Math.max(c, d)));
cache[i][j] = max;

return max;
}
}``````

• this solution is great and run time can beats 90% java code

• The comments really helps especially for the noobies...thanks

• This might be nit-picky. Since negative integers in the given array are allowed, I think the code doesn't work when the first value on the solution path is Integer.MIN_VALUE. How do you think about changing Integer.MIN_VALUE to Long.MIN_VALUE?

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