Key idea: compute the longest length starting from every index `(i, j)`

in the matrix. This can be done by DFS. That is, at location `(i, j)`

, we have 4 possible increasing directions, so we check every direction. If one direction satisfies the increasing requirement, increase longest[i][j] by 1. We stop searching when we reach a local maximum. Here, a local maximum refers to the index where none of its four neighbors is less than it. The `helper`

function is to compute the longest length starting from `(i, j)`

. We store longest[i][j] once it is computed.

We don't know where the ultimate longest length starts from, so we need to check every possible index if it is not already computed, and that's what the `for`

loop in the main function is about.

As of time complexity, we check every index only once, so time complexity is `O(mn)`

.

A final little detail, the original matrix is expanded so that we don't need to consider all kinds of boundary issues. If original matrix is

```
* * * *
* * * *
* * * *
```

The extended matrix would be like follows:

```
0 ∞ ∞ ∞ ∞ 0
∞ * * * * ∞
∞ * * * * ∞
∞ * * * * ∞
0 ∞ ∞ ∞ ∞ 0
```

Ideally the four corners should be ∞ but since it does not matter (it is not reachable in the code), I will leave it as is. Thanks to @dietpepsi for pointing out the mistake in my previous extended matrix

```
public int longestIncreasingPath(int[][] matrix) {
int rows = matrix.length;
if(rows<1) return 0;
int cols = matrix[0].length;
int[][] matrixExt = new int[rows+2][cols+2], longest = new int[rows+2][cols+2]; // extended matrix and result matrix
for(int i=1; i<rows+1; i++) {
matrixExt[i][0] = matrixExt[i][cols+1] = 0x7fffffff;
for(int j=1; j<cols+1; j++) {
matrixExt[0][j] = matrixExt[rows+1][j] = 0x7fffffff;
matrixExt[i][j] = matrix[i-1][j-1];
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 4 different directions
int max = 1;
for(int i=1; i<rows+1; i++) {
for(int j=1; j<cols+1; j++) {
int temp = helper(matrixExt, longest, dirs, rows, cols, i, j);
max = temp > max ? temp : max;
}
}
return max;
}
private int helper(int[][] matrix, int[][] longest, int[][] dirs, int rows, int cols, int i, int j) {
if(longest[i][j]>0) return longest[i][j]; // reuse
int max = 1; // result
for(int[] d : dirs) {
if(matrix[i][j] > matrix[i+d[0]][j+d[1]]) {
int temp = helper(matrix, longest, dirs, rows, cols, i+d[0], j+d[1]) + 1; // recursively update longest[i][j]
max = temp > max ? temp : max;
}
}
longest[i][j] = max; // store for reuse
return max;
}
```