LeetCode: Lonely Pixel II

LeetCode: Lonely Pixel II

Given a picture consisting of black and white pixels, and a positive integer N, 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

The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Input:                                            
[['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'W', 'B', 'W', 'B', 'W']]

N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
        0    1    2    3    4    5         column index                                            
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
row index

Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels.
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.

Note:

The range of width and height of the input 2D array is [1,200].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        if (picture == null || picture.length < N || picture[0] == null || picture[0].length < N) {
            return 0;
        }

        Map<Integer, Integer> colMap = new HashMap<>();
        Map<Integer, Integer> rowMap = new HashMap<>();
        Map<Integer, List<Integer>> sameRowMap = new HashMap<>();
        int result = 0;

        for (int i = 0; i < picture.length; i++) {
            for (int j = 0; j < picture[0].length; j++) {
                if (picture[i][j] == 'B') {
                    colMap.put(j, colMap.getOrDefault(j, 0) + 1);
                    rowMap.put(i, rowMap.getOrDefault(i, 0) + 1);
                }
            }
        }

        for (int i = 0; i < picture.length; i++) {
            for (int j = 0; j < picture[0].length; j++) {
                if (picture[i][j] == 'B') {
                    List<Integer> rows = sameRowMap.getOrDefault(j, new ArrayList<>());
                    rows.add(i);
                    sameRowMap.put(j, rows);
                }
            }
        }

        for (Map.Entry<Integer, List<Integer>> entry : sameRowMap.entrySet()) {
            List<Integer> val = entry.getValue();
            int R = val.get(0);
            boolean allSame = true;
            for (int i = 1; i < val.size(); i++) {
                if (!isSameRow(picture[R], picture[val.get(i)])) {
                    allSame = false;
                    break;
                }
            }

            if (allSame &&
                    colMap.getOrDefault(entry.getKey(), 0) == N &&
                    rowMap.getOrDefault(R, 0) == N) {
                result += val.size();
            }

        }

        return result;
    }

    private boolean isSameRow(char[] a, char[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) return false;
        }
        return true;
    }
}