Java O(nm) time, 23 ms, only iterate the Matrix once


  • 0

    Time: O(MN+M), only need to iterate the matrix onece
    Space: O(2M+N)

    Time and Space tradeoff:
    It's possible to use only O(M) or O(N) space;
    But the Time will be O(2MN);

    public class Solution {
        public int findLonelyPixel(char[][] picture) {
            if(picture==null||picture.length==0||picture[0].length==0) return 0;
            int[] rowCount=new int[picture.length]; //number of black in each row
            int[] colCount=new int[picture[0].length]; //number of black in each col
            int[] blackPos=new int[picture.length]; //Remember the first black position of reach row
            int res=0, rows=picture.length, cols=picture[0].length;
            for(int r=0; r<rows; r++){
                for(int c=0; c<cols; c++){
                    if(picture[r][c]=='B'){
                        rowCount[r]++; 
                        colCount[c]++;
                        if(rowCount[r]<2) blackPos[r]=c;
                    }
                }
            }
            for(int r=0; r<rows;r++){
                if(rowCount[r]!=1) continue;
                if(colCount[blackPos[r]]!=1) continue;
                res++;
            }
            return res;
        }
    }
    

Log in to reply
 

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