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).
Example 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:
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.
Example 3:
Input: matrix = [[1]] Output: 1
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 2000 <= matrix[i][j] <= 231 - 1
Solution #1 : Using DFS (Brute Force)
Here we check whether that array is the beginning of our largest increasing pattern or not.
we check for the maximum length one can get from the sides and return the maximum since we only need a path and not the area.
Here we Do it for each element in the array !!
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
//C++ //Yellow Coding class Solution { public: int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int ans =0; int dfs(vector<vector<int>>& matrix,int n,int m,int x,int y, int preVal){ if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size()) return 0; if (matrix[x][y] <= preVal) return 0; int MAX =1; for(int k=0;k<4;k++) { int X= x+dx[k],Y= y+dy[k]; MAX = max(MAX, 1 + dfs(matrix,n,m, X, Y,matrix[x][y])); } return MAX; } int longestIncreasingPath(vector<vector<int>>& matrix) { int n = matrix.size(); if(n==0) return 0; int m = matrix[0].size(); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ ans = max(ans, dfs(matrix,n,m,i,j,INT_MIN)); } } return ans; } }; |
Time Complexity :
O((N*M)*4^(N*M))
We are calculating longest path for each cell and for each cell we are invoking 4 additional functions. All those invoked functions may further call 4 additional functions and this may continue maximum of N*M times taking the overall time complexity to O((N*M)*4^(N*M)).
We can see that 4 further functions are invoked only the first time solve is called and each subsequent time we only make 3 additional calls at max. So we can put O((N*M)*3^(N*M)) as a more tighter upper bound of the given solution.
Space Complexity :
O((N*M))
Solution #2 : Using DFS + DP(Memoization)
We have to realize that in the above solution, we were doing a lot of repeated calculation which can be avoided if we use dynamic programming to store the previously calculated results.
For eg. If we have calculated optimal path for matrix[0][0] and suppose that it is – (0,0) -> (0, 1) -> (0, 2) -> (1, 2) ->(1, 1) ->(1, 0), which is 6 in length. Now, for finding the optimal path for matrix[0][1], there’s no need to recalculate the path again because it is part of optimal path of matrix[0][0] and for getting the optimal path for matrix[0][0], we must also have gotten the optimal path of its adjacent visitable cells. So, optimal answer for matrix[0][1] could have directly been returned as 5 if we had used DP.
From the above, it is apparent that the naive brute force approach has –
👉 Many overlapping subproblems – As already seen in the example above, once we calculate the optimal answer for a cell, we most probably have also recursed for its adjacent cells and calculated the optimal answers for them as well. There’s no need to repeat the same calculations again.
👉 The problem has optimal substructure property meaning that the solutions of bigger problems can be calculated from optimal solutions of its sub-problems. So, if there’s a longest path (optimal solution) for a given cell starting at that cell, all the cells in its path must also have optimal paths as well starting at those cells respectively.
So, the repeated recalculation of sub-problems can be avoided using dp as given below –
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
// // Yellow Coding class Solution { public: int dx[4]={0,0,-1,1}; int dy[4]={-1,1,0,0}; int dfs(vector<vector<int>>& matrix,int n,int m,int x,int y, int preVal,vector<vector<int>>& dp){ //Boundary check if (x < 0 || x >= matrix.size() || y < 0 || y >= matrix[0].size()) return 0; if (matrix[x][y] <= preVal) return 0; //Check already computed or not if(dp[x][y]!=-1) return dp[x][y]; // minimum path from each cell is always atleast 1 dp[x][y] =1; //Go in each direction, and check which path yields the maximum length path // This is giving TLE, so we will have to memoize the code for(int k=0;k<4;k++) { int X= x+dx[k],Y= y+dy[k]; dp[x][y] = max(dp[x][y], 1 + dfs(matrix,n,m, X, Y, matrix[x][y],dp)); // adding 1, to include the current cell in the path } return dp[x][y]; } int longestIncreasingPath(vector<vector<int>>& matrix) { int n = matrix.size(); if(n==0) return 0; int m = matrix[0].size(); // dp[i][j] will store maximum path length starting from matrix[i][j] vector<vector<int>> dp(n, vector<int>(m, -1)); // minimum path from each cell is always atleast 1 int ans=1; // calculating maximum path from each cell and at last returning the maximum length for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ ans = max(ans, dfs(matrix,n,m,i,j,INT_MIN,dp)); } } return ans; } }; |
Here we save the maximum path that particular element can give and save it in an array dp .
That path will be the maximum path for that element since we are traversing in all possible directions in each recursion.
Thus we reduce our time complexity from O( N * N * 4^N) to O(N*N)
