# 533 Lonely Pixel II

## 533. [Lonely Pixel II](https://leetcode.com/problems/lonely-pixel-ii/description/)

## 1. Question

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

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

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

## 2. Implementation

**(1) Hash Table**

思路: 这道题让我们找到有多少个黑色pixel它们所处的位置满足以下两个条件:

1.黑色pixel所在的行和列的黑色pixel个数都是N，这个和lonely pixel 1类似

2.在第i列包含黑色pixel的所有行中，它们都必须是一样的。这里的**一样**指的是**行里的pixel的排列是一样的。**

因为第二个条件的存在,所以我们必须用一个方法表示行的排列，这里可以利用每行的pixel排列作为key，然后放在一个hashmap里。当我们将所有行的排列都转成string的key放在hashmap后， 再遍历这个map，由于题目的要求, 只有当map.get(key) 等于 N时，我们才继续查看每列中的黑色pixel的个数是否为N以及当前列的pixel是否为黑色pixel，如果是的话 count 加N. 由于我们只关心黑色pixel个数为N的行，所以在getRowKey(), 如果当前行的黑色pixel个数不为N，我们直接返回empty string

```java
public class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        if (picture == null || picture.length == 0) {
            return 0;
        }

        int m = picture.length, n = picture[0].length;
        int[] colCount = new int[n];

        // Use string at each row as key in map, so all the same row will share the same key
        // Map will help us to address rule 2
        Map<String, Integer> map = new HashMap<>();


        for (int i = 0; i < m; i++) {
            String key = getRowKey(picture, i, colCount, N);
            if (key.length() != 0) {
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }

        int count = 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) {
                        count += N;
                    }
                }
            }
        }
        return count;
    }

    // Convert pixels at each row to string
    public String getRowKey(char[][] picture, int row, int[] colCount, int N) {
        int rowCount = 0;
        StringBuilder key = new StringBuilder();

        for (int j = 0; j < picture[0].length; j++) {
            key.append(picture[row][j]);
            if (picture[row][j] == 'B') {
                ++rowCount;
                ++colCount[j];
            }
        }
        return rowCount == N ? key.toString() : "";
    }
}
```

**(2) 简洁版**

```java
class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        if (picture == null || picture.length == 0) {
            return 0;
        }

        int m = picture.length, n = picture[0].length;
        int[] row = new int[m];
        int[] col = new int[n];

        Map<String, Integer> map = new HashMap();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (picture[i][j] == 'B') {
                    ++row[i];
                    ++col[j];
                }
            }

            if (row[i] == N) {
                String key = new String(picture[i]);
                map.put(key, map.getOrDefault(key, 0) + 1);
            }
        }

        int count = 0;

        for (String key : map.keySet()) {
            if (map.get(key) == N) {
                for (int j = 0; j < n; j++) {
                    if (key.charAt(j) == 'B' && col[j] == N) {
                        count += N;
                    }
                }
            }
        }
        return count;
    }
}
```

## 3. Time & Space Complexity

**Hash Table:** 时间复杂度O(mn), 空间复杂度O(m + n)


---

# 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://protegejj.gitbook.io/algorithm-practice/leetcode/graph/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.