32ms 2-pass Java O(mn) Time with O(1) Space


  • 0
    public int findLonelyPixel(char[][] picture) {
        int count = 0;
        int w = picture[0].length;
        int h = picture.length;
        
        // 1st pass, scan row by row
        for(int i=0; i<h; i++) {
            int bCount = 0;
            int bi = -1, bj = -1;
            for(int j=0; j<w; j++) {
                if(picture[i][j]=='B') {
                    bCount++;
                    bi = i;
                    bj = j;
                    picture[i][j] = 'C';
                }
            }
            if(bCount==1) {
                picture[bi][bj] = 'B';
            }
        }
        
        // 2nd pass, scan col by col
        for(int j=0; j<w; j++) {
            int bCount = 0;
            int cCount = 0;
            for(int i=0; i<h; i++) {
                if(picture[i][j]=='C') {
                    picture[i][j] = 'B'; // recover the array
                    cCount++;
                } else if(picture[i][j]=='B')
                    bCount++;
            }
            if(cCount==0 && bCount==1)
                count++;
        }
        return count;
    }

Log in to reply
 

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