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

# 329. Longest Increasing Path in a Matrix

Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

nums = \[ \[9,9,4], \[6,6,8], \[2,1,1] ]

Return 4

The longest increasing path is \[1, 2, 6, 9].

Example 2:

nums = \[ \[3,4,5], \[3,2,6], \[2,2,1] ]

Return 4

The longest increasing path is \[3, 4, 5, 6]. Moving diagonally is not allowed.

Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

## Solution <a href="#solution" id="solution"></a>

```java
public class Solution {
public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null) return 0;
        int row = matrix.length;
        if (row == 0) {
            return 0;
        }

        int column = matrix[0].length;
        int[][] dp = new int[row][column];
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < column; j ++) {
                dp[i][j] = -1;
            }
        }

        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < column; j ++) {
                dfs(i,j, row, column, matrix, dp);
            }
        }

        int max = dp[0][0];

        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < column; j ++) {
                max = Math.max(dp[i][j], max);
            }
        }

        return max;
    }

    private int dfs(int x, int y, int row, int column, int[][] matrix, int[][] dp) {
        if (dp[x][y] != -1) {
            return dp[x][y];
        }

        if (x - 1 >= 0 && matrix[x][y] < matrix[x - 1][y]) {
            dp[x][y] = Math.max(1 + dfs(x - 1, y, row, column, matrix, dp), dp[x][y]);
        }

        if (x + 1 <= row - 1 && matrix[x][y] < matrix[x + 1][y]) {
            dp[x][y] = Math.max(1 + dfs(x + 1, y, row, column, matrix, dp), dp[x][y]);

        }

        if (y - 1 >= 0 && matrix[x][y] < matrix[x][y - 1]) {
            dp[x][y] = Math.max(1 + dfs(x, y - 1, row, column, matrix, dp), dp[x][y]);

        }

        if (y + 1 <= column - 1 && matrix[x][y] < matrix[x][y + 1]) {
            dp[x][y] = Math.max(1 + dfs(x, y + 1, row, column, matrix, dp), dp[x][y]);
        }

        if (dp[x][y] == -1) {
            dp[x][y] = 1;
        }

        return dp[x][y];
    }
}
```