CPP Solution (2 ways) DFS, BFS with Explanation
There seem to be a lack of explanation in all the CPP contributions even for some voted highly. So here\'s one with explanations. \n\nSkip to (2) if you want th
There seem to be a lack of explanation in all the CPP contributions even for some voted highly. So here\'s one with explanations. \n\n**Skip to (2) if you want the working solution**\n\nFirst Attempt: *Solution1 class*\n(1) The idea is for every single cell, we want to check if it can reach the atlantic, pacific, none, or both. I first started with two separate functions, one for checking the atlantic and one for checking pacific and then comparing the two...but this is too inefficient so I merged the two functions. \n\nWe know we can reach the pacific if we ended at row 0 or col 0 and the atlantic if we reached last row and last column, so these are the base case. But there is also a special case where we can jump from a NONE state to a BOTH state which is when we reached the \'hot corners\' the upper right and bottom left which are connected to both the atlantic and pacific.\n\nTo check if we can reach the edges, it\'s simple: we just need to do either BFS or DFS (recursive or iterative with stacks). So from that cell we see if water can spill to its neighbours and the neighbours\' neighbours etc. \n\n```\n\nclass Solution1 {\nprivate: \n    \n    enum class State\n    {\n        PACIFIC,\n        ATLANTIC, \n        BOTH, \n        NONE\n    };\n     \n    int rowSize, colSize;\n    vector<int> offset = {0, 1, 0, -1, 0};\n    \n    bool outOfBounds(int row, int col){\n        return row < 0 || col < 0 || row >= rowSize || col >= colSize;\n    }\n    \n    State flowToPacificOrAtlantic(vector<vector<int>>& matrix, int row, int col, vector<vector<bool>> visited, State prevState){       \n        if (prevState == State::BOTH)\n            return State::BOTH;\n        \n        \n        if((row == rowSize -1 && col == 0) || (row == 0 && col== colSize -1)) // top right and bottom left (Special corners)\n            return State::BOTH;\n        \n        // Update the state: We can only go from None to Pacific or Atlantic or from Pacific or Atlantic to both from here on. \n        if (row == 0 || col == 0){ // Pacific Ocean\n            if (prevState == State::ATLANTIC){ \n                return prevState = State::BOTH; // We already previously reached the atlantic, so we change the state to both\n            } else{\n                prevState = State::PACIFIC;\n            }\n        } else if (row == rowSize -1 || col== colSize -1){ // Atlantic Ocean\n            if (prevState == State::PACIFIC){\n                return prevState = State::BOTH; // We already previously reached the pacific, so we change the state to both\n            } else {\n                prevState = State::ATLANTIC;\n            }\n        }\n        \n        // We need to keep track of the visited ones for cycles since we are checking equal water levels as well which means we can get\n        // stuck in a cycle of the same values\n        visited[row][col] = true; \n        \n        int currWaterLevel = matrix[row][col];\n        for (int i = 1; i<offset.size(); i++){ // Go to left right up down using the offset --> (+1, +0) (+0, +1), (-1, +0), (+0, -1)\n            int r = row + offset[i], c = col + offset[i-1]; // assign variable to record the row and col of the up down left right \n            if(!outOfBounds(r , c) && \n               currWaterLevel >= matrix[r][c] && // current water level is higher than the surrounding water\n               !visited[r][c]){\n                \n                prevState = flowToPacificOrAtlantic(matrix, r, c, visited, prevState); // Update the state\n            }\n        }\n        return prevState;\n    }\n    \npublic:\n    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {\n        vector<vector<int>> result;\n        rowSize = matrix.size(); \n        if (rowSize == 0)\n            return result;\n        colSize = matrix[0].size();\n        \n        \n        vector<vector<bool>> visited(rowSize, vector<bool> (colSize, 0));\n        for (int row = 0; row < rowSize; row++){\n            for (int col = 0; col<colSize; col++){\n                if (flowToPacificOrAtlantic(matrix, row, col, visited, State::NONE) == State::BOTH){\n                    result.push_back({row, col});\n                }\n            }\n        }     \n        return result;\n    }\n};\n```\n\nBut since we are recursing over every single cell for a very large m and n, this becomes very inefficeint. All we really need to do is to check for the edges and find how far the pacific ocean and atlantic ocean spill respectively. This is where the second approach comes in. \n\nSecond Solution: *Solution class*\n(2) The second approach is much more efficient as mentioned before. We need to record the \'map\' of where the pacific  and atlantic ocean can spill into. So we need two separate maps one for the atlantic and one for the pacific. Once done, we just compare to see where the common areas where both the atlantic and pacific water can \'spill upwards\' from the edges. By spill upwards I mean imagine the water from the edges flowing up hill, hence we are looking for bigger numbers. This is just the reverse logic from (1).  \n\n\n\n```\n\nclass Solution {\nprivate: \n\n    int rowSize, colSize;\n    vector<int> offset = {0, 1, 0, -1, 0};\n    \n    bool outOfBounds(int row, int col){\n        return row < 0 || col < 0 || row >= rowSize || col >= colSize;\n    }\n    \n    void flowToPacificOrAtlantic(vector<vector<int>>& matrix, int row, int col, vector<vector<bool>>& visited){       \n        visited[row][col] = true; \n        \n        int currWaterLevel = matrix[row][col];\n        for (int i = 1; i<offset.size(); i++){ // Go to left right up down using the offset --> (+1, +0) (+0, +1), (-1, +0), (+0, -1)\n            int r = row + offset[i], c = col + offset[i-1]; \n            if(!outOfBounds(r , c) && \n               currWaterLevel <= matrix[r][c] && // !!! current water level is lower than the surrounding water !!!\n               !visited[r][c]){\n                \n                flowToPacificOrAtlantic(matrix, r, c, visited);\n            }\n        }\n    }\n    \npublic:\n    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {\n        vector<vector<int>> result;\n        rowSize = matrix.size(); \n        if (rowSize == 0)\n            return result;\n        colSize = matrix[0].size();\n        \n        // initialize the maps to 0\n        vector<vector<bool>> pacific(rowSize, vector<bool> (colSize, 0)); \n        vector<vector<bool>> atlantic(rowSize, vector<bool> (colSize, 0));\n\n        for (int row = 0; row < rowSize; row++){\n            flowToPacificOrAtlantic(matrix, row, 0, pacific); // column 0 (pacific)\n            flowToPacificOrAtlantic(matrix, row, colSize -1, atlantic); // column end (atlantic)\n        }    \n        for (int col = 0; col < colSize; col++){\n             flowToPacificOrAtlantic(matrix, 0, col, pacific); // row 0 (pacific)\n             flowToPacificOrAtlantic(matrix, rowSize -1, col, atlantic); // row end (atlantic)\n        }\n\n        // Compare the two \'maps\' and find where they have a common 1\n        for (int row = 0; row<rowSize; row++){\n            for(int col = 0; col<colSize; col++){\n                if (pacific[row][col] == 1 && atlantic[row][col] == 1){\n                    result.push_back({row, col});\n                }\n            }   \n        }\n        \n        return result;\n    }\n};\n\n```\n\nEdit: \nI am adding BFS rather than the DFS for finding the visited matrix. This code is very similar to DFS except it uses a queue which prevents additional space incurred by use of the call stack. Just change ```flowToPacificOrAtlantic``` to ```BFS``` from solution 2 and everything should work. \n\n```\nvoid BFS(vector<vector<int>> & matrix, int row, int col, vector<vector<bool>> &visited){\n        queue<pair<int, int>> todo;\n        todo.push(make_pair(row, col));\n        visited[row][col] = 1;\n        while (!todo.empty()){\n            pair<int, int> p = todo.front(); \n            int currWaterLevel = matrix[p.first][p.second];\n            todo.pop(); \n            // check neighbours of todo\n            for (int i = 1; i<offset.size(); i++){\n                int r = p.first + offset[i], c =  p.second + offset[i-1];\n                if (!outOfBounds(r, c) && currWaterLevel <= matrix[r][c] && !visited[r][c]){\n                    todo.push(make_pair(r, c));\n                    visited[r][c] = 1;\n                }\n            }\n        }\n    }\n```
[]