19ms C++ O(mn^2) solution

  • 0

    Let R store the row indices of those rows with N black pixels and C store the column indices of those columns with N black pixels.

    We iterate through all the columns in C. In each such column, we find the first row in R such that picture[R[k]][C[j]] is a black pixel. Then we count all the rows that are equal to the R[k]-th row and add that number to the total count of the lonely pixels. The reason is these rows also have a black pixel in the C[j]-th column.

    If a black pixel in the C[j]-th column belongs to a row that is not equal to R[k]-th row, then there is not a single lonely pixel in the C[j]-th column. We continue the search for the lonely pixels in the next column in C.

    class Solution {
        int findBlackPixel(vector<vector<char>>& picture, int N) {
            if( picture.empty() ) return 0;
            int row = picture.size(), col = picture[0].size();
            vector<int> R,C;
            for(int i=0;i<row;i++){
                int count = 0;
                for(int j=0;j<col;j++){
                    if( picture[i][j]=='B' ) count++;
                if( count==N ) R.push_back(i);
            for(int i=0;i<col;i++){
                int count = 0;
                for(int j=0;j<row;j++){
                    if( picture[j][i]=='B' ) count++;
                if( count==N ) C.push_back(i);
            if( C.empty() || R.empty() ) return 0;
            int total_count = 0;
            for(int j=0;j<C.size();j++){
                int s = 1;
                int k = 0;
                while( k<R.size() && picture[R[k]][C[j]]=='W' ) k++;
                if( k==R.size() ) continue;
                int p=0;
                while( p<row ){
                    if( p!=R[k] && picture[p][C[j]]=='B' ){
                        if( picture[p]==picture[R[k]] ) s++;
                        else {s=0;break;}
                total_count += s;
            return total_count;

Log in to reply

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