0533. Lonely Pixel II.md

0533. Lonely Pixel II, medium, locked, freq: 0p%, acceptance: 46.3%

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:

Row R and column C both contain exactly N black pixels. 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: 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].

[["W","B","W","B","B","W"],["B","W","B","W","W","B"],["W","B","W","B","B","W"],["B","W","B","W","W","B"],["W","W","W","B","B","W"],["B","W","B","W","W","B"]] 3 [["W","W","W","B","B","W"],["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","W","B","W","B","W"]] 3 [["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","W","B","W","B","W"]] 3 [["W","B","W","W","W","W"],["W","W","W","B","B","W"],["W","W","W","B","B","W"],["W","W","B","W","B","W"]] 1

// 64ms, 88%
class Solution {
public:
    int findBlackPixel(vector<vector<char>>& picture, int N) {
        if (picture.empty()) return 0;
        
        int R = picture.size();
        int C = picture[0].size();
        vector<int> rows(R, 0);
        vector<int> cols(C, 0);
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (picture[i][j] == 'B') {
                    rows[i]++;
                    cols[j]++;
                }
            }
        }
        int res = 0;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (picture[i][j] == 'B') {
                    if (cols[j] == N && rows[i] == cols[j]) {
                        // check all rows below
                        int k = i+1;
                        int cc = 1; // row i
                        while (k < R) {
                            if (picture[k][j] == 'B') {
                                if (rows[k] == rows[i] && picture[i] == picture[k])
                                    cc++;
                                else {
                                    cc = -1;
                                    break;
                                }
                            }
                            k++;
                        }
                        if (cc > 0) {
                            res += cc;
                        }
                        cols[j] = -1;
                    } else {
                        cols[j] = -1;
                    }
                }
            }
        }
        return res;
    }
};