Java Solution using two HashMaps


  • 0

    The idea is to maintain two HashMaps:

    1. rowMap is row-signature -> list of row indices share this row-signature
    2. colMap is the encoded string of row indices of black pixel along a col -> count

    So for each row-signature, we can extract its row indices, encoded into string and lookup in colMap.

    public int findBlackPixel(char[][] picture, int N) {
        Map<String, List<Integer>> rowMap = new HashMap<>();
        Map<String, Integer> colMap = new HashMap<>();
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<picture.length; i++) {
            sb.setLength(0);
            int n = 0;
            for(int j=0; j<picture[0].length; j++) {
                sb.append(picture[i][j]);
                if(picture[i][j]=='B')
                    n++;
            }
            if(n!=N)
                continue;
            String rowStr = sb.toString();
            if(!rowMap.containsKey(rowStr))
                rowMap.put(rowStr, new ArrayList<Integer>());
            rowMap.get(rowStr).add(i);
        }
        
        for(int j=0; j<picture[0].length; j++) {
            sb.setLength(0);
            int n = 0;
            for(int i=0; i<picture.length; i++) {
                if(picture[i][j]=='B') {
                    sb.append(i).append("_");
                    n++;
                }
            }
            if(n!=N)
                continue;
            String rowStr = sb.substring(0,sb.length()-1);
            colMap.put(rowStr, colMap.getOrDefault(rowStr,0)+1);
        }
        
        int count = 0;
        for(Map.Entry<String, List<Integer>> entry : rowMap.entrySet()) {
            sb.setLength(0);
            for(int i : entry.getValue())
                sb.append(i).append("_");
            String rowStr = sb.substring(0,sb.length()-1);
            count += entry.getValue().size() * colMap.getOrDefault(rowStr,0);
        }
        
        return count;
    }

Log in to reply
 

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