Java, O(nm), scan matrix twice, with exlpanation


  • 0
    D
    public class Solution {
        public int findLonelyPixel(char[][] picture) 
        {
            char[][] p = picture;
            if (p == null || p.length == 0 || p[0].length == 0) { return 0; }
            
            Set<Integer> notLonely = new HashSet<>();
            
            int row = p.length;
            int col = p[0].length;
            
            int num = 0;
        
            // scan each row
            for (int i = 0; i < row; i++)
            {   
                Queue<Integer> que = new LinkedList<>();
                for (int j = 0; j < col; j++)
                {
                    if (p[i][j] == 'B')
                    {
                        que.add(i * col + j);
                    }
                }
                // if queur size > 1, means 'B' in this line are not qualified
                if (que.size() > 1) { notLonely.addAll(que); }
            }
            
            // scan each column
            for (int i = 0; i < col; i++)
            {
                Queue<Integer> que = new LinkedList<>();
                for (int j = 0; j < row; j++)
                {
                    if (p[j][i] == 'B')
                    {
                        que.add(j * col + i); 
                    }
                }
                // if queue size is 1, check if this 'B' is in notLonely set? if not, it is qualified
                // here no need to care queue size > 2 situation, because they are not qualified
                if (que.size() == 1 && !notLonely.contains(que.peek()))
                {
                    num++;
                }
            }
            return num;
        }
    }
    

Log in to reply
 

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