Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Linked List Data Structure | Creation and Traversal

Introduction: In this tutorial we will create our linked list. Before writing code let's understand key words related to linked list: 1. Head:    first node of the linked list is called the head of the list. and this node is most important. 2.Tail:       last node is called the tail of the list which must points to  null.            step1: For creating the list first of all let's declare the structure of Nodes of the list: struct Node{ int val; struct Node *next; } step2: write main function: int main(){     int n;     cout<<"enter the number of Nodes:";     cin>>n;     struct Node* head = NULL;     struct Node* temp;     int m;     while(n--){         cout<<"enter the data into nodes:";         cin>>m;    ...
1 comment
Read more

Target Sum | Backtracking Problem

Introduction: In this tutorial we are going to solve a problem "Target Sum" which is from leetcode. and believe me it's really a good problem to understand Backtracking(Recursion). and if you try to understand the problem as well as code you will get a clear picture of Backtracking. Problem Statement: Link To Problem You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and - . For each integer, you should choose one from + and - as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Solution: As given in question, we have two operation + and -. so we will make recursive call for + and - . and if we have sum as target and we have reached upto the last ind...
Post a Comment
Read more

Construct Binary Tree from preorder and inorder | Data Structure

Introduction: In this tutorial we are going to see how we can construct the binary tree from given preorder and inorder. Prerequisites: you should know about binary tree traversal and on paper you can draw binary tree from given preorder and inorder traversal. Inorder:left->root->right; Preorder:root->left->right; Problem Statement: we have given two arrays. one for preorder and another for inorder. by using these two array we have to built a binary tree. eg: preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] solution: Solution: We will follow recursive approach to solve this question.let's discuss how we can solve it. Trick: In the given preorder the very first element will be the root of the tree. then we will find root element in inorder also. and we know in inorder traversal we have left part then root and then right part of the tree. by using preorder we can get the root of the main tree and by using inorder and root we can get the left part and right part of the...
Post a Comment
Read more