Verbose Java O(m*n) Solution, HashMap


  • 32

    The difficult parts are validating the two rules:

    1. Row R and column C both contain exactly N black pixels.
    2. For all rows that have a black pixel at column C, they should be exactly the same as row R

    My solution:

    1. Scan each row. If that row has N black pixels, put a string signature, which is concatenation of each characters in that row, as key and how many times we see that signature into a HashMap. Also during scan each row, we record how many black pixels in each column in an array colCount and will use it in step 2.
      For input:
      [['W', 'B', 'W', 'B', 'B', 'W'],
      ['W', 'B', 'W', 'B', 'B', 'W'],
      ['W', 'B', 'W', 'B', 'B', 'W'],
      ['W', 'W', 'B', 'W', 'B', 'B']]
      We will get a HashMap:
      {"WBWBBW": 3, "WWBWBB": 1}
      and colCount array:
      [0, 3, 1, 3, 4, 1]
    2. Go through the HashMap and if the count of one signature is N, those rows potentially contain black pixels we are looking for. Then we validate each of those columns. For each column of them has N black pixels (lookup in colCount array), we get N valid black pixels.
      For above example, only the first signature "WBWBBW" has count == 3. We validate 3 column 1, 3, 4 where char == 'B', and column 1 and 3 have 3 'B', then answer is 2 * 3 = 6.

    Time complexity analysis:
    Because we only scan the matrix for one time, time complexity is O(m*n). m = number of rows, n = number of columns.

    public class Solution {
        public int findBlackPixel(char[][] picture, int N) {
            int m = picture.length;
            if (m == 0) return 0;
            int n = picture[0].length;
            if (n == 0) return 0;
            
            Map<String, Integer> map = new HashMap<>();
            int[] colCount = new int[n];
            
            for (int i = 0; i < m; i++) {
                String key = scanRow(picture, i, N, colCount);
                if (key.length() != 0) {
                    map.put(key, map.getOrDefault(key, 0) + 1);
                }
            }
            
            int result = 0;
            for (String key : map.keySet()) {
                if (map.get(key) == N) {
                    for (int j = 0; j < n; j++) {
                        if (key.charAt(j) == 'B' && colCount[j] == N) {
                            result += N;
                        }
                    }
                }
            }
            
            return result;
        }
        
        private String scanRow(char[][] picture, int row, int target, int[] colCount) {
            int n = picture[0].length;
            int rowCount = 0;
            StringBuilder sb = new StringBuilder();
            
            for (int j = 0; j < n; j++) {
                if (picture[row][j] == 'B') {
                    rowCount++;
                    colCount[j]++;
                }
                sb.append(picture[row][j]);
            }
            
            if (rowCount == target) return sb.toString();
            return "";
        }
    }
    

  • 0

    Same idea here unless I forget to use the HashMap part :(


  • 4
    W

    i don't know what's the meaning of rule 2


  • 6
    F

    Great work for using hashmap to store the string of rows. So that we don't need to check rule 2, which is really awesome!

    Just a suggestion, since you already traversed all picture in your part 1. You could keep using the int[] cols to store the count for each columns. It will help us to save some time instead of using scanCol.

    Here is my solution for your reference.

    public int findBlackPixel(char[][] picture, int N) {
            if (picture == null || picture.length == 0 || picture[0].length == 0) return 0;
            int m = picture.length, n = picture[0].length;
            int[] cols = new int[n];
            Map<String, Integer> map = new HashMap<>();
            
            for (int i = 0; i < m; i++) {
                int count = 0;
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (picture[i][j] == 'B') {
                        cols[j]++;
                        count++;
                    }
                    sb.append(picture[i][j]);
                }
                if (count == N) {
                    String curRow = sb.toString();
                    map.put(curRow, map.getOrDefault(curRow, 0) + 1);
                }
            }
            
            int res = 0;
            for (String row : map.keySet()) {
                if (map.get(row) != N) continue;
                for (int i = 0; i < n; i++) {
                    if (row.charAt(i) == 'B' && cols[i] == N) {
                        res += N;
                    }
                }
            }
            return res;
        }
    

  • 0

    @Free9 You are right. Updated my post, thanks!


  • 0

    at first I thought "exactly the same as row R" mentioned in rule 2 means the number of black pixels should be same.......
    then I'm really confused why we should use map.get(key)==N......
    I wasted half an hour......


  • 0

    @shawngao said in Verbose Java O(m*n) Solution, HashMap:

        int m = picture.length;
        if (m == 0) return 0;
        int n = picture[0].length;
        if (n == 0) return 0;
    

    Is it possible that m != 0 but n == 0 ?
    if (n == 0) return 0; this is redundant.


  • 0

    @zzhai It's totally possible. Try this:

    int[][] a = new int[10][0];
    System.out.println(a[0].length);
    

  • 0

    @shawngao

    Got it. Thanks.


  • 0

    said in Verbose Java O(m*n) Solution, HashMap:

    if(map.get(key) == N)

    Can anyone help explain why this matters? I can not interpret rule 2 to this...

    For instance, in this test case if there are only two signatures are identical, is the answer still 6? or in your logic, 0?


  • 0

    @awwwyellow According to the problem, our task is to:

    Find the number of black pixels located at some specific row R and column C that align with all the following rules:
    1.Row R and column C both contain exactly N black pixels.
    2.For all rows that have a black pixel at column C, they should be exactly the same as row R

    Look at the red B in the example in my post, it satisfy rule 1 when N = 3. To satisfy rule 2, for each B in column 1, that row (which are row 1 and 2) should be exactly the same as row 0. In this case, they are the same. So the red B is a Lonely Pixel.
    [['W', 'B', 'W', 'B', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'B', 'W'],
    ['W', 'B', 'W', 'B', 'B', 'W'],
    ['W', 'W', 'B', 'W', 'B', 'B']]

    Back to your question, if there are only two signatures are identical, the answer is 0. Check the following example:
    [['W', 'B', 'W', 'B', 'B', 'W'],
    ['B', 'B', 'W', 'B', 'W', 'W'],
    ['W', 'B', 'W', 'B', 'B', 'W'],
    ['W', 'W', 'B', 'W', 'B', 'B']]
    Those red B satisfy rule 1 but all failed rule 2.


  • 0

    @shawngao

    Thank you for the answer in detail! Really appreciate it!

    Now I know that I missed a very obvious thing, that is, in rule 2

    1. For all rows that have a black pixel at column C...

    Since qualified column C can only have N black pixels, there should be exactly N column R. And only when they are identical, those black pixels count.


  • 0

    @shawngao great solution, I've got the same here but I've optimized on the "row key" by converting the pixel string to an array of longs then to a string by concatenating the longs which should yield a much more compact row key.

        public int FindBlackPixel(char[,] picture, int N) 
        {
            int n = picture.GetLength(0);
            int m = picture.GetLength(1);
            int[] rowCnts = new int[n];
            int[] colCnts = new int[m];
            string[] rowKeys = new string[n];
            Dictionary<string, int> rowKeyMap = new Dictionary<string,int>();
            
            for (int i = 0; i < n; i++)
            {
                long[] keyArr = new long[(m+63)/64];
                for (int j = 0; j < m; j++)
                {
                    if (picture[i,j] == 'B')
                    {
                        rowCnts[i]++;
                        colCnts[j]++;
                        keyArr[j/64] |= (long)1 << (j % 64); 
                    }
                }
                
                string key = "";
                foreach (long x in keyArr) key+= x.ToString() + ",";
                
                rowKeys[i] = key;
                if (!rowKeyMap.ContainsKey(key)) rowKeyMap[key] = 0;
                rowKeyMap[key]++;
            }
            
            int lonelyCnt = 0;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                {
                    if (picture[i,j] == 'B' && rowCnts[i] == N && colCnts[j] == N && rowKeyMap[rowKeys[i]] == N)
                    {
                        lonelyCnt++;
                    }
                }
            }
            
            return lonelyCnt;
        }
    

  • 0
    N

    @Free9 in if (row.charAt(i) == 'B' && cols[i] == N)
    I believe row.charAt(i) == 'B' is redundant.


  • 0
    L

    Nice solution. A small optimization - StringBuilder is not required. You can simply do -

    if (rowCount == target) return new String(picture[row]);


  • 0
    F

    Here is my code, cannot be compared to yours.

    public class Solution {
        public int findBlackPixel(char[][] picture, int N) {
            int count = 0, R = picture.length, C = picture[0].length;
            int[] row = new int[R];
            int[] col = new int[C];
            HashMap<Integer,String> map = new HashMap<>();
            for(int i = 0;i<R;i++){
                StringBuilder sb = new StringBuilder();
                for(int j = 0;j<C;j++){
                    sb.append(picture[i][j]);
                    if(picture[i][j] == 'B'){
                        row[i]++;
                        col[j]++;
                    }
                }
                map.put(i,sb.toString());
            }
            for(int i = 0;i<R;i++){
                for(int j = 0;j<C;j++){
                    if(picture[i][j] == 'B'){
                        if(row[i] == N && col[j] == N){
                            int n = 0;
                            for(int k = 0;k<R && n < N;k++){
                                if(picture[k][j] == 'B'){
                                    if(!map.get(i).equals(map.get(k))) break;
                                    n++;
                                }
                            }
                            if(n == N) count++;
                        }
                    }
                }
            }
            return count;
        }
    }
    

  • 0
    S

    @shawngao said in Verbose Java O(m*n) Solution, HashMap:

    Beautiful solution : Was confused a bit on why there is map.get(key) == N check. Finally got it. The code map.get(key) == N ensures that there are at least N Black (B) pixels in the column C and the code cols[i] == N further ensures that there are exactly N black pixels (no other row has black pixel at that position) in column C.


  • -1
    M

    Thanks for sharing.
    I have a space-cost optimization.
    Actually, we don't need to store a hard-copy of a row's values, we can just store the row's reference pointer.
    Here is my code:

    class Solution {
        public int findBlackPixel(char[][] picture, int N) {
            if(picture==null || picture.length==0 || picture[0].length==0)
                return 0;
            
            int m=picture.length;
            int n=picture[0].length;
            int[] cols = new int[n]; 
            
            Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();
            Map<Integer, char[]> rowMap = new HashMap<Integer, char[]>();
            for(int i=0; i<m; i++){
                int count=0; //count number of 'B' in current row 
                for(int j=0; j<n; j++)
                    if(picture[i][j]=='B'){
                        cols[j]++;
                        count++;
                    }
                
                if(count==N){ //if current row has the desired number of 'B' 
                    int hash = Arrays.hashCode( picture[i] );
                    countMap.put( hash, countMap.getOrDefault(hash, 0)+1 );  //put the reference of the current row, rather than the hard copy
                    rowMap.putIfAbsent(hash, picture[i]);  
                }
            }
            
            int result=0; 
            for(Map.Entry<Integer, Integer> entry : countMap.entrySet())
                if( entry.getValue()==N ){ //if there are N rows, all of which are the same
                    char[] row = rowMap.get( entry.getKey() );
                    for(int j=0; j<n; j++)
                        if(row[j]=='B' && cols[j]==N) //current position is 'B', current col also has N 'B'
                            result += N;
                }
            
            return result; 
        }
    }
    

Log in to reply
 

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