Sponsored
Sponsored
This approach uses a combination of Depth First Search (DFS) and memoization to solve the problem efficiently. We explore each cell, attempting to find the longest increasing path starting from that cell. To avoid recalculating the path length for each call from the same cell, we use memoization to store already computed results.
The time complexity is O(m * n) because each cell is computed once and cached. The space complexity is also O(m * n) due to the memoization table.
1class Solution {
2 public int longestIncreasingPath(int[][] matrix) {
3 if (matrix.length == 0) return 0;
4 int m = matrix.length, n = matrix[0].length;
5 int[][] memo = new int[m][n];
6 int maxLen = 0;
7 for (int i = 0; i < m; i++) {
8 for (int j = 0; j < n; j++) {
9 maxLen = Math.max(maxLen, dfs(matrix, i, j, memo));
10 }
11 }
12 return maxLen;
13 }
14
15 private int dfs(int[][] matrix, int x, int y, int[][] memo) {
16 if (memo[x][y] != 0) return memo[x][y];
17 int m = matrix.length, n = matrix[0].length;
18 int maxLen = 1;
19 int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
20 for (int[] d : directions) {
21 int nx = x + d[0], ny = y + d[1];
22 if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {
23 int len = 1 + dfs(matrix, nx, ny, memo);
24 maxLen = Math.max(maxLen, len);
25 }
26 }
27 memo[x][y] = maxLen;
28 return maxLen;
29 }
30}This Java solution uses a recursive DFS method dfs to explore all possible increasing paths from the current cell, storing intermediate results in a memoization table to avoid redundant calculations. Each cell's path length is calculated and cached, ensuring an efficient solution.
This approach systematically calculates the longest increasing path dynamically by first iterating over the matrix and then updating results based on previously computed values. By using a dynamic programming table, we determine, for each cell, the longest chain it can contribute to incrementally.
The time complexity is O(m * n) due to the fact that each matrix cell can be a starting point and is only calculated once with memoization guidance. The space complexity is O(m * n) because a result is stored for each cell in the DP table.
1public class Solution {
2 public int LongestIncreasingPath(int[][] matrix) {
3 if (matrix == null || matrix.Length == 0) return 0;
4 int m = matrix.Length, n = matrix[0].Length;
int[][] dp = new int[m][];
for (int i = 0; i < m; i++) dp[i] = new int[n];
int maxLen = 0;
int dfs(int x, int y) {
if (dp[x][y] != 0) return dp[x][y];
int[][] directions = new int[][]{new int[]{-1, 0}, new int[]{1, 0}, new int[]{0, -1}, new int[]{0, 1}};
dp[x][y] = 1;
foreach (var dir in directions) {
int nx = x + dir[0], ny = y + dir[1];
if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
dp[x][y] = Math.Max(dp[x][y], 1 + dfs(nx, ny));
}
}
return dp[x][y];
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
maxLen = Math.Max(maxLen, dfs(i, j));
}
}
return maxLen;
}
}This C# solution follows a similar logic by using dynamic programming principles. The DFS function explores potential paths from each cell, leveraging an array dp to store already calculated results and determine the longest increasing path starting from a specific point.