Straightforward efficient C++ solution using stack


  • 3

    The code is rather long, but very easy to understand.
    Basically, we use two tables to record if the water can flow to pacific or atlantic. To determine the element, we use a stack structure to search the element on the four sides of a certain element.
    In the test the runtime is 55ms.

    class Solution {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            vector<pair<int,int>> result;
            int m=matrix.size();
            if (m==0) return result;
            int n=matrix[0].size();
            int pacific[m][n];
            int atlantic[m][n];
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    pacific[i][j]=0;
                    atlantic[i][j]=0;
                }
            }
            stack<pair<int,int>> sp;
            stack<pair<int,int>> sa;
            for (int i=0;i<m;i++){
                pacific[i][0]=1;
                sp.push(make_pair(i,0));
            }
            for(int i=1;i<n;i++){
                pacific[0][i]=1;
                sp.push(make_pair(0,i));
            }
            while(!sp.empty()){
                pair<int, int> index=sp.top();
                int x=index.first;
                int y=index.second;
                sp.pop();
                if (x-1>=0&&pacific[x-1][y]==0&&matrix[x-1][y]>=matrix[x][y]){
                    sp.push(make_pair(x-1,y));
                    pacific[x-1][y]=1;
                }
                if (x+1<m&&pacific[x+1][y]==0&&matrix[x+1][y]>=matrix[x][y]){
                    sp.push(make_pair(x+1,y));
                    pacific[x+1][y]=1;
                }
                if (y-1>=0&&pacific[x][y-1]==0&&matrix[x][y-1]>=matrix[x][y]){
                    sp.push(make_pair(x,y-1));
                    pacific[x][y-1]=1;
                }
                if (y+1<n&&pacific[x][y+1]==0&&matrix[x][y+1]>=matrix[x][y]){
                    sp.push(make_pair(x,y+1));
                    pacific[x][y+1]=1;
                }
            }
            for (int i=0;i<m;i++){
                atlantic[i][n-1]=1;
                sa.push(make_pair(i,n-1));
            }
            for(int i=0;i<n-1;i++){
                atlantic[m-1][i]=1;
                sa.push(make_pair(m-1,i));
            }
            while(!sa.empty()){
                pair<int, int> index=sa.top();
                int x=index.first;
                int y=index.second;
                sa.pop();
                if (x-1>=0&&atlantic[x-1][y]==0&&matrix[x-1][y]>=matrix[x][y]){
                    sa.push(make_pair(x-1,y));
                    atlantic[x-1][y]=1;
                }
                if (x+1<m&&atlantic[x+1][y]==0&&matrix[x+1][y]>=matrix[x][y]){
                    sa.push(make_pair(x+1,y));
                    atlantic[x+1][y]=1;
                }
                if (y-1>=0&&atlantic[x][y-1]==0&&matrix[x][y-1]>=matrix[x][y]){
                    sa.push(make_pair(x,y-1));
                    atlantic[x][y-1]=1;
                }
                if (y+1<n&&atlantic[x][y+1]==0&&matrix[x][y+1]>=matrix[x][y]){
                    sa.push(make_pair(x,y+1));
                    atlantic[x][y+1]=1;
                }
            }
            for(int i=0; i<m;i++){
                for(int j=0;j<n;j++){
                    if (atlantic[i][j]==1&&pacific[i][j]==1){
                        result.push_back(make_pair(i,j));
                    }
                }
            }
            return result;
        }
    };
    
    

  • 0
    I

    @liyouvane Thank you so much for your solution..


  • 0

    Glad it helps.


  • 0
    D

    @liyouvane Thanks for sharing. I changed the coding style.

    class Solution {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            vector<pair<int,int>> res;
            if (matrix.empty()) return res;
            int m = matrix.size(), n = matrix[0].size();
            vector<vector<bool>> p(m, vector<bool>(n, false));
            vector<vector<bool>> a(m, vector<bool>(n, false));
            stack<pair<int, int>> sp;
            stack<pair<int, int>> sa;
            for (int i = 0; i < m; i++)
            {
                p[i][0] = true;
                sp.push(make_pair(i, 0));
                
                a[i][n-1] = true;
                sa.push(make_pair(i, n-1));            
            }
            for(int j = 0; j < n; j++)
            {
                p[0][j] = true;
                sp.push(make_pair(0, j));
                
                a[m-1][j] = true;
                sa.push(make_pair(m-1, j));            
            }
            int dir[5] = {0, 1, 0, -1, 0};
            while(!sp.empty())
            {
                auto ij = sp.top(); sp.pop();
                int i = ij.first, j = ij.second;
                for (int d = 0; d < 4; d++)
                {
                    int x = i + dir[d], y = j + dir[d+1];
                    if (x >= 0 && x < m && y >= 0 && y < n)
                    {
                        if (!p[x][y] && matrix[x][y] >= matrix[i][j])
                        {
                            sp.push(make_pair(x, y));
                            p[x][y] = true;
                        }
                    }
                }
            }
            while(!sa.empty())
            {
                auto ij = sa.top(); sa.pop();
                int i = ij.first, j = ij.second;
                for (int d = 0; d < 4; d++)
                {
                    int x = i + dir[d], y = j + dir[d+1];
                    if (x >= 0 && x < m && y >= 0 && y < n)
                    {
                        if (!a[x][y] && matrix[x][y] >= matrix[i][j])
                        {
                            sa.push(make_pair(x, y));
                            a[x][y] = true;
                        }
                    }
                }
            }
            for(int i = 0; i < m; i++)
            {
                for(int j = 0; j < n; j++)
                {
                    if (p[i][j] && a[i][j])
                    {
                        res.push_back(make_pair(i, j));
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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