Can someone please take a look at my code and help me find what's wrong with it?


  • 0
    K

    I tried a DFS approach where I created a separate recursive function to get the result for one ocean and called it twice for both oceans and returned the intersection of the result from the two functions. I don't think the recursive back tracking function works on edge cases so I handled that in the for loop before calling the recursive functions. For the test case it gives all the correct positions but it also adds 3 incorrect positions [3,4], [4,3] and [4,4]. Any help would be appreciated, Thanks!

    class Solution {
    public:
        
        bool reachOcean(vector<vector<int>>& matrix, set<pair<int, int>>& result, int ocean, int i, int j) // ocean: 0 for pacific and 1 for atlantic
        {
            int xOffset, yOffset, xEdge, yEdge;
            if(ocean == 0) // pacific
                xOffset = -1, yOffset = -1, xEdge = 0, yEdge = 0;
            else
                xOffset = 1, yOffset = 1, xEdge = matrix[0].size() - 1, yEdge = matrix.size() - 1;
            if(i == xEdge || j == yEdge)
                return true;
            
            if(matrix[i + xOffset][j] > matrix[i][j] && matrix[i][j + yOffset] > matrix[i][j])
            {
                //cout << i << ", " << j << endl;
                return false;
                
            }
            bool reached = reachOcean(matrix, result,ocean, i + xOffset, j) || reachOcean(matrix, result,ocean, i, j + yOffset);
            if(reached) result.insert(pair<int,int>(i,j));
            return true;
        }
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) 
        {
            set<pair<int,int>> atlantic, pacific;
            vector<pair<int, int>> result;
            for(int i = 0; i < matrix.size(); i++)
            {
                for(int j = 0; j < matrix[0].size(); j++)
                {
                    if(i == 0 || j == 0) 
                        pacific.insert(pair<int,int>(i, j));
                    else
                        reachOcean(matrix, pacific,0 ,i ,j);
                    if(i == matrix.size() - 1 || j == matrix[0].size() - 1)
                        atlantic.insert(pair<int, int>(i, j));
                    else
                        reachOcean(matrix, atlantic,1 ,i ,j );
                 //   cout << "End:" << endl;
                }
            }
            set_intersection(pacific.begin(),pacific.end(),atlantic.begin(),atlantic.end(), std::back_inserter(result));
            return result;
    
            
            
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.