LeetCode 329: Longest Increasing Path in a Matrix
Problem Description
Explanation
To solve this problem, we can use a dynamic programming approach along with depth-first search (DFS) to find the longest increasing path in the matrix starting from each cell. We will store the length of the longest increasing path starting at each cell in a separate 2D array. We will then iterate through each cell in the matrix and perform a DFS from that cell to find the longest increasing path.
Algorithm:
- Initialize a 2D array
dpto store the length of the longest increasing path starting from each cell. - Initialize a variable
maxPathto store the maximum path length found so far. - Iterate through each cell in the matrix and perform DFS from that cell to find the longest increasing path.
- During the DFS, for each neighboring cell that has a greater value, recursively call the DFS from that cell and update the length of the path.
- Keep track of the maximum path length found during the DFS.
- Return the maximum path length as the result.
Time Complexity: O(mn) where m is the number of rows and n is the number of columns in the matrix. Space Complexity: O(mn) for the dp array.
Solutions
class Solution {
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public int longestIncreasingPath(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int maxPath = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxPath = Math.max(maxPath, dfs(matrix, dp, i, j));
}
}
return maxPath;
}
private int dfs(int[][] matrix, int[][] dp, int i, int j) {
if (dp[i][j] != 0) {
return dp[i][j];
}
int maxPath = 1;
for (int[] dir : dirs) {
int x = i + dir[0];
int y = j + dir[1];
if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length && matrix[x][y] > matrix[i][j]) {
maxPath = Math.max(maxPath, 1 + dfs(matrix, dp, x, y));
}
}
dp[i][j] = maxPath;
return maxPath;
}
}Related LeetCode Problems
Loading editor...