Doubt on DFS algorithm

#1

I did this problem LeetCode 417 Pacific Atlantic Waterflow
my code passed 71 test cases out of 113 my friend did using the same logic and his solution got accepted but I am stuck can you please help me figure out the error.

Link-https://ide.codingblocks.com/s/350437
https://leetcode.com/problems/pacific-atlantic-water-flow/

#2

hello @mridulmohanbagri17
pass ur matrix by refernce

#3

Okay trying to do and will let you know.

#4

I have passed it using reference sir,but it’s not working

#5 
class Solution {
public:
    int n,m;
    pair<int,int> moves[4]={{0,-1},{0,1},{1,0},{-1,0}};
    void dfs(vector<vector<int>> &matrix,int r,int c,int prevHeight,bool** ocean)
    {

        if(r<0 or c<0 or r>n-1 or c>m-1 or matrix[r][c]<prevHeight or ocean[r][c])
            return;
        ocean[r][c]=true;
        for(auto x:moves)
        {
            dfs(matrix,r+x.first,c+x.second,matrix[r][c],ocean);
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) 
    {
        vector<vector<int>> result;
        n=matrix.size();
        if(n==0)
            return result;
        m=matrix[0].size();

        
        
        bool** pacific_check=new bool*[n];
        for(int i=0;i<n;i++)
        {
            pacific_check[i]=new bool[m];
        }
        
        bool** atlantic_check=new bool*[n];
        for(int i=0;i<n;i++)
        {
            atlantic_check[i]=new bool[m];
        }
        for(int i=0;i<n;i++)
	    {
		for(int j=0;j<m;j++)
		{
			pacific_check[i][j]=false;
		}
	    }
        
        for(int i=0;i<n;i++)
	    {
		for(int j=0;j<m;j++)
		{
			atlantic_check[i][j]=false;
		}
	    }
        //TOP TO BOTTOM
        for(int i=0;i<n;i++)
        {
            dfs(matrix,i,0,matrix[i][0],pacific_check);
            dfs(matrix,i,m-1,matrix[i][m-1],atlantic_check);
        }
        //LEFT TO RIGHT
        for(int i=0;i<m;i++)
        {
            dfs(matrix,0,i,matrix[0][i],pacific_check);
            dfs(matrix,n-1,i,matrix[n-1][i],atlantic_check);
        }
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(pacific_check[i][j] and atlantic_check[i][j]){
                    vector<int> v;
                    v.push_back(i);
                    v.push_back(j);
                    result.push_back(v);
                }
            }
        }
        return result;
    }
};

it is working

image

#6

Thankyou very much sir,it’s working and sorry for troubling with such a silly mistake.

#7

Can you please let me know why error occured.

#8

@mridulmohanbagri17
it is simple when we pass vector as reference then same vector is passed i.e no copy is created but when we pass vector as value then a new vector is created and all the data from original vector is copied to newly created vector.
because of this extra/unnecessary copying time ur solution was giving tle

#9

Ohh I got it ,thankyou sir I was so confused regarding this problem.Thankyou very much.