# 533. 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:**<br>

```
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:**<br>

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

{% hint style="info" %}
題目的意思是要找到一個'B' grid，他的同一個row上和同一個col上，都有N個'B'。而且沿著col上下要有N個row長一樣。
{% endhint %}

{% hint style="info" %}
建立row和col arrays紀錄每個row/col出現多少次B。並且把每個row的array轉成一個string存在row2str裡，方便之後用row index定位到該row的array。\
再把整個input 2D grid掃一遍，如果遇到某個grid的同個row/col上有N個B，那就固定那個col index往下掃描不同的row，檢查是否有N個row相等。如果找到相等的情形，把res更新之後要記得把col array歸零避免之後看到又重複計算。
{% endhint %}

```cpp
int findBlackPixel(vector<vector<char>>& picture, int N) { // time: O(m * n); space: O(m * n)
    if (picture.empty() || picture[0].empty()) return 0;
    int m = picture.size(), n = picture[0].size();
    vector<int> row(m, 0), col(n, 0);
    vector<string> row2str(m, "");
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            row2str[i].push_back(picture[i][j]);
            if (picture[i][j] == 'B') {
                ++row[i];
                ++col[j];
            }
        }
    }
    int res = 0, k;
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (row[i] == N && col[j] == N) {
                for (k = 0; k < m; ++k) {
                    if (picture[k][j] == 'B') {
                        if (row2str[i] != row2str[k])
                            break;
                    }
                }
                if (k == m) {
                    res += col[j];
                    col[j] = 0; // reset to 0 to avoid dupliacte calculation
                }
            }
        }
    }
    return res;
}
```

{% hint style="info" %}
一樣需要先掃描input 2D grid一遍，紀錄每個col index對應到的col有多少B在同個col上。並且用cur同時紀錄B在該row出現的數量，如果該row有N個B，那就把該row的array轉成string，當作unordered\_map的key記錄下來。\
然後再traverse unordered\_map裡的entry，看看是否有string出現N次的，有的話就traverse那個string看看有沒有char是'B'而且該col的B總數為N。找到的話就可以在res上加N。
{% endhint %}

```cpp
int findBlackPixel(vector<vector<char>>& picture, int N) { // time: O(m * n); space: O(m * n)
    if (picture.empty() || picture[0].empty()) return 0;
    int m = picture.size(), n = picture[0].size();
    vector<int> col(n, 0);
    unordered_map<string, int> mp;
    for (int i = 0; i < m; ++i) {
        int cur = 0; // how many 'B's in the current row
        for (int j = 0; j < n; ++j) {
            if (picture[i][j] == 'B') {
                ++col[j];
                ++cur;
            }
        }
        if (cur == N) 
            ++mp[string(picture[i].begin(), picture[i].end())];
    }
    int res = 0;
    for (auto& a : mp) {
        if (a.second != N) continue;
        for (int j = 0; j < n; ++j) {
            if (a.first[j] == 'B' && col[j] == N)
                res += N;
        }
    }
    return res;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/array/533.-lonely-pixel-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.