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.
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 int longestIncreasingPath(vector<vector<int>>& matrix) {
7 if (matrix.empty() || matrix[0].empty()) return 0;
8 int m = matrix.size(), n = matrix[0].size();
9 vector<vector<int>> memo(m, vector<int>(n, -1));
10 int maxLen = 0;
11
12 std::function<int(int, int)> dfs = [&](int x, int y) {
13 if (memo[x][y] != -1) return memo[x][y];
14 vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
15 int max_len = 1;
16 for (const auto& d : directions) {
17 int nx = x + d.first, ny = y + d.second;
18 if (nx >= 0 && nx < m && ny >= 0 && ny < n && matrix[nx][ny] > matrix[x][y]) {
19 max_len = max(max_len, 1 + dfs(nx, ny));
20 }
21 }
22 memo[x][y] = max_len;
23 return max_len;
24 };
25
26 for (int i = 0; i < m; ++i) {
27 for (int j = 0; j < n; ++j) {
28 maxLen = max(maxLen, dfs(i, j));
29 }
30 }
31 return maxLen;
32 }
33};In this C++ solution, we utilize a lambda function for the DFS which captures the variables by reference and uses the memoization technique to store results of previously computed paths. This approach efficiently calculates the longest increasing path starting from each cell and stores the result in the memo table to prevent redundant calculations.
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.
1var longestIncreasingPath = function(matrix)
The JavaScript solution uses dynamic programming. For each cell, the function dfs recursively explores valid neighbors, resulting in the longest increasing path starting from that cell. The result for each cell is stored in a DP table before being returned, which ensures efficiency by preventing the recalculation of already known results.