• Time:O(mn)
• Space:O(mn)

C++

``````class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
const int m = matrix.size();
const int n = matrix[0].size();
int ans = 0;
vector<vector<int>> memo(m, vector<int>(n));

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = max(ans, dfs(matrix, i, j, INT_MIN, memo));

return ans;
}

private:
// memo[i][j] := the LIP starting from matrix[i][j]
int dfs(const vector<vector<int>>& matrix, int i, int j, int prev,
vector<vector<int>>& memo) {
if (i < 0 || i == matrix.size() || j < 0 || j == matrix[0].size())
return 0;
if (matrix[i][j] <= prev)
return 0;
int& ans = memo[i][j];
if (ans)
return ans;

const int curr = matrix[i][j];
return ans = 1 + max({dfs(matrix, i + 1, j, curr, memo),
dfs(matrix, i - 1, j, curr, memo),
dfs(matrix, i, j + 1, curr, memo),
dfs(matrix, i, j - 1, curr, memo)});
}
};
``````

JAVA

``````class Solution {
public int longestIncreasingPath(int[][] matrix) {
final int m = matrix.length;
final int n = matrix[0].length;
int ans = 0;
// memo[i][j] := the LIP starting from matrix[i][j]
int[][] memo = new int[m][n];

for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
ans = Math.max(ans, dfs(matrix, i, j, Integer.MIN_VALUE, memo));

return ans;
}

private int dfs(int[][] matrix, int i, int j, int prev, int[][] memo) {
if (i < 0 || i == matrix.length || j < 0 || j == matrix[0].length)
return 0;
if (matrix[i][j] <= prev)
return 0;
if (memo[i][j] > 0)
return memo[i][j];

final int curr = matrix[i][j];
final int a = dfs(matrix, i + 1, j, curr, memo);
final int b = dfs(matrix, i - 1, j, curr, memo);
final int c = dfs(matrix, i, j + 1, curr, memo);
final int d = dfs(matrix, i, j - 1, curr, memo);
return memo[i][j] = 1 + Math.max(Math.max(a, b), Math.max(c, d));
}
}
``````

Python

``````class Solution:
def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
m = len(matrix)
n = len(matrix[0])

@lru_cache(None)
def dfs(i: int, j: int, prev: int) -> int:
if i < 0 or i == m or j < 0 or j == n:
return 0
if matrix[i][j] <= prev:
return 0

curr = matrix[i][j]
return 1 + max(dfs(i + 1, j, curr),
dfs(i - 1, j, curr),
dfs(i, j + 1, curr),
dfs(i, j - 1, curr))

return max(dfs(i, j, -math.inf) for i in range(m) for j in range(n))
``````