Given an m x n integers matrix, return the length of the longest increasing path in matrix.
From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).
Test Cases
Example 1:
| 9 | 9 | 4 |
| 6 | 6 | 8 |
| 2 | 1 | 1 |
Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].
Example 2:
| 3 | 4 | 5 |
| 3 | 2 | 6 |
| 2 | 2 | 1 |
Input: matrix = [[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.
Solution
class Solution {
public:
int dir[5] = {-1, 0, 1, 0, -1};
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, 0));
int mx = 1;
for(int i=0; i<m; i++) {
for(int j=0; j<n; j++) {
mx = max(mx, dfs(i, j, matrix, dp, m, n));
}
}
return mx;
}
int dfs(int i, int j, vector<vector<int>> &matrix, vector<vector<int>> &dp, int m, int n) {
if (dp[i][j] != 0) return dp[i][j];
int mx = 1;
for(int k=0; k<4; k++) {
int x = i+dir[k], y = j+dir[k+1];
if (x < 0 || y < 0 || x >= m || y >= n || matrix[x][y] <= matrix[i][j]) continue;
mx = max(mx, 1+dfs(x, y, matrix, dp, m, n));
}
return dp[i][j] = mx;
}
};class Solution {
public int longestIncreasingPath(int[][] matrix) {
int n = matrix.length, m = matrix[0].length;
int[][] dp = new int[n][m];
int max = 1;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
max = Math.max(max, dfs(matrix, dp, i, j, n, m));
}
}
return max;
}
private int dfs(int[][] matrix, int[][] dp, int i, int j, int n, int m) {
if (dp[i][j] != 0) return dp[i][j];
int[] dir = new int[]{-1, 0, 1, 0, -1};
int max = 1;
for(int k=0; k<4; k++) {
int x = i+dir[k], y = j+dir[k+1];
if (x<0 || y<0 || x>=n || y>=m || matrix[x][y] <= matrix[i][j]) continue;
max = Math.max(max, 1+dfs(matrix, dp, x, y, n, m));
}
dp[i][j] = max;
return max;
}
}