DFS Application | Longest Increasing Path in a Matrix

Intoduction:

In this tutorial we are going to solve a problem from leetcode, which is a good problem for applying recursion on 2D matrix or how can we apply DFS on 2D matrix.

Question Link : Leetcode

Input: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Solution:

So basically what we are going to do is making recursive calls in all four direction.

Approach1: Recursion(this will fail in last three test cases) and that's why we will use approach2.

Full Code:

    int helper(vector<vector<int>>& matrix, int x, int y, int val, int flag, int temp){
        if(x<0 || x>=matrix.size() || y<0 || y>=matrix[x].size()){
            return temp;
        }
        if( flag!=0 && matrix[x][y]>val){
            temp++;
        }
        if(flag!=0 && matrix[x][y]<=val){
            return temp;
        }
        int ll = helper(matrix, x-1,y, matrix[x][y],1,temp);// up
        int lr = helper(matrix, x+1,y, matrix[x][y],1,temp); //down
        int lb = helper(matrix, x,y-1, matrix[x][y],1,temp); //left
        int lt = helper(matrix, x,y+1, matrix[x][y],1,temp);//right
        return max(max(ll,lr),max(lb,lt));
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int maxcount=0;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
               int count = helper(matrix,i,j,matrix[i][j],0,1);
                if(count>maxcount)
                    maxcount=count;
            }
        }
        return maxcount;
    }

Approach2: Recursion with Memoization

Full Code:

 int helper(vector<vector<int>>& matrix, int x, int y, int val, int flag, int temp, vector<vector<int>>&dp){
        if(x<0 || x>=matrix.size() || y<0 || y>=matrix[x].size()){
            return temp;
        }
        if(flag!=0 && matrix[x][y]<=val){
            return temp;
        }
        if(dp[x][y]!=-1 && matrix[x][y]>val){
            return dp[x][y];
        }
       /* if( flag!=0 && matrix[x][y]>val){
            temp++;
        }*/

        int ll = helper(matrix, x-1,y, matrix[x][y],1,temp,dp);
        int lr = helper(matrix, x+1,y, matrix[x][y],1,temp,dp);
        int lb = helper(matrix, x,y-1, matrix[x][y],1,temp,dp);
        int lt = helper(matrix, x,y+1, matrix[x][y],1,temp,dp);
        if(dp[x][y]==-1)
            dp[x][y]=1+max(max(ll,lr),max(lb,lt));
        return 1+max(max(ll,lr),max(lb,lt));
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int maxcount=1;
        if(matrix.size()==0){
            return 0;
        }
        vector<vector<int>>dp(matrix.size(),vector<int>(matrix[0].size(),-1));
        for(int i=0;i<dp.size();i++){
            for(int j=0;j<dp[i].size();j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                if(dp[i][j]==-1){
                    int count = helper(matrix,i,j,matrix[i][j],0,0,dp);
                    if(count>maxcount)
                        maxcount=count;
                }
                else{
                    if(dp[i][j]>maxcount)
                        maxcount=dp[i][j];
                }
            }
        }
        return maxcount;
    }

Conclusion:

we are basically making four recursive calls for each direction. and then returning max of all those 4 values. To memoise already calculated path we have a 2D vector and it will increase the efficiency of our program.