C++ 25 lines beats 90%~ish


  • 0
    B

    Main idea is pretty simple, needs a O(m*n) space to store the scoring vector, each element gets its rightmost bit set to 1 if it can reach the Pacific, and its 2nd rightmost bit set to 1 if it can reach the Atlantic. And we push the resulting pair to the output if both bits are 1 (so the actual value of the element equals 3).

    The helper function takes the previous elevation as an input, to check if the current element is of higher elevation, and only changes the current bit if it's higher than the previous element.

    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            if (matrix.empty()) return vector<pair<int,int>>();
            int m=matrix.size(), n=matrix.front().size();
            vector<vector<int>> scores(m,vector<int>(n,0));
            vector<pair<int,int>> out;
            for (int r=0; r<m; r++) {
                for (int c=0; c<n; c++) {
                    if (r==0 || c==0) helper(matrix,scores,out,r,c,1,matrix[r][c]);
                    if (r==m-1 || c==n-1) helper(matrix,scores,out,r,c,2,matrix[r][c]);
                }
            }
            return out;
        }
        void helper(vector<vector<int>>& matrix, vector<vector<int>>& scores, vector<pair<int,int>>& out,
                        int r, int c, int mask, int prev) {
            if (r>=0 && r<matrix.size() && c>=0 && c<matrix.front().size()
                    && ((scores[r][c]&mask)==0) && matrix[r][c]>=prev) {
                scores[r][c]+=mask;
                if (scores[r][c]==3) out.push_back(make_pair(r,c));
                helper(matrix,scores,out,r,c-1,mask,matrix[r][c]);
                helper(matrix,scores,out,r+1,c,mask,matrix[r][c]);
                helper(matrix,scores,out,r,c+1,mask,matrix[r][c]);
                helper(matrix,scores,out,r-1,c,mask,matrix[r][c]);
            }
        }
    

Log in to reply
 

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