> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/dfs-and-bfs/329.-longest-increasing-path-in-a-matrix.md).

# 329. Longest Increasing Path in a Matrix

```java
class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] memo = new int[m][n];
        int result = 0;
        for(int i=0; i<m; i++){
            for (int j=0; j<n; j++){
               result = Math.max(result, dfs(matrix, memo, i, j)); 
            }
        }
        return result;
    }
    
    private int dfs(int[][] matrix, int[][] memo, int i, int j){
        if(memo[i][j]!=0) return memo[i][j];
        int left = (j-1>=0 && matrix[i][j-1]>matrix[i][j]) ? 
                    dfs(matrix, memo, i, j-1) : 0;
        int right = (j+1<matrix[0].length && matrix[i][j+1]>matrix[i][j]) ? dfs(matrix, memo, i, j+1) : 0;
        int top = (i-1>=0 && matrix[i-1][j]>matrix[i][j])? dfs(matrix, memo, i-1, j) : 0;
        int down = (i+1<matrix.length && matrix[i+1][j]>matrix[i][j]) ? dfs(matrix, memo, i+1, j) : 0;
        int maxLen = Math.max(Math.max(left, right), Math.max(top, down))+1;
        memo[i][j]=maxLen;
        return maxLen;
    }
}
```