Java O(nm) time O(n + m) space 25ms beats 100%


  • 0
    W
    public class Solution {
        public int findLonelyPixel(char[][] picture) {
            if (picture == null || picture.length == 0 || picture[0].length == 0) return 0;
            final int m = picture.length;
            final int n = picture[0].length;
            
            int[] rows = new int[m];//-1: no black pixels so far. >= 0: previous lonely pixel's col index. -2: more than one black pixel seen.
            int[] cols = new int[n];//-1: no black pixels so far. >= 0: previous lonely pixel's row index. -2: more than one black pixel seen
            Arrays.fill(rows, -1);
            Arrays.fill(cols, -1);
            for (int j = 0; j < n; j++) {
                //loop through n columns.
                for (int i = 0; i < m; i++) {
                    if (picture[i][j] != 'B') continue;//if not black, see next pixel
                    //update rows
                    if (rows[i] == -1) {
                        rows[i] = j;
                    } else if (rows[i] >= 0) {
                        rows[i] = -2;
                    }//else rows[i] == -2, then we keep it as is.
                    //update cols
                    if (cols[j] == -1) {
                        cols[j] = i;
                    } else if (cols[j] >= 0) {
                        cols[j] = -2;
                    }
                }
            }
            int res = 0;
            for (int i = 0; i < m; i++) {
                if (rows[i] >= 0 && cols[rows[i]] >= 0) res++;
            }
            return res;
        }
    }
    

Log in to reply
 

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