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(rowCount[r]<2) blackPos[r]=c;
            for(int r=0; r<rows;r++){
                if(rowCount[r]!=1) continue;
                if(colCount[blackPos[r]]!=1) continue;
            return res;

Log in to reply

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