# 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:

``````Input: nums =
[
[9,9,4],
[6,6,8],
[2,1,1]
]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
``````

Example 2:

``````Input: nums =
[
[3,4,5],
[3,2,6],
[2,2,1]
]
Output: 4
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.
``````

Intuition:

## Solution

DFS + DP - (12ms 55.81% AC)

``````class Solution {
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] memo = new int[m][n];
int max = 0;

for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
max = Math.max(max, findPath(matrix, i, j, memo));
}
}
return max;
}

int findPath(int[][] matrix, int i, int j, int[][] memo) {
if (memo[i][j] != 0) return memo[i][j];
int m = matrix.length;
int n = matrix[0].length;
int tempLength = 0;
int[] di = new int[] {
0,
1,
0,
-1
};
int[] dj = new int[] {
1,
0,
-1,
0
};

for (int k = 0; k < 4; k++) {
int ni = i + di[k];
int nj = j + dj[k];
if (ni >= 0 && nj >= 0 && ni < m && nj < n) {
if (matrix[ni][nj] > matrix[i][j]) {
tempLength = Math.max(tempLength, findPath(matrix, ni, nj, memo));
}
}
}
tempLength++;
memo[i][j] = tempLength;
return tempLength;
}
}
``````