[c++] o(mn) time o(n) space. beats 100% lol


  • 0
    J

    Pretty sure someone will come up with faster solutions soon, but for the time being I'm getting 182ms and beats other solutions :)
    Lol this is a great step for a newbie!

    Scanning through row by row.
    Using

    1. vector<int> to mark the accumulated column 'B' count
    2. index to mark accumulated row 'B' count
    int findLonelyPixel(vector<vector<char>>& picture) {
        int m = picture.size();
        if (m==0)
            return 0;
        int n =picture[0].size();
        if (n==0)
            return 0;
        int res = 0;
        vector<int> col(n+1, 0);
        for (int i=0; i<m; i++) {
            int index = -1;
            for (int j=0; j<n; j++) {
                if (picture[i][j]=='B') {
                    if(col[j]++==1)
                        res--;
                    
                    if(index>=0) {
                        col[index]=2;
                        col[j]=2;
                        index=n;
                    } else {
                        index = col[j]==1? j:n;
                    }
                }
            }
            if (index > -1 && index < n)
                res++;
        }
        return res;
    }
    

    };


Log in to reply
 

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