# 533 Lonely Pixel II

## 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. 1.
Row R and column C both contain exactly N black pixels.
2. 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. 1.
The range of width and height of the input 2D array is [1,200].

## 2. Implementation

(1) Hash Table

1.黑色pixel所在的行和列的黑色pixel个数都是N，这个和lonely pixel 1类似
2.在第i列包含黑色pixel的所有行中，它们都必须是一样的。这里的一样指的是行里的pixel的排列是一样的。

public class Solution {
public int findBlackPixel(char[][] picture, int N) {
if (picture == null || picture.length == 0) {
return 0;
}
int m = picture.length, n = picture.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.length; j++) {
key.append(picture[row][j]);
if (picture[row][j] == 'B') {
++rowCount;
++colCount[j];
}
}
return rowCount == N ? key.toString() : "";
}
}
(2) 简洁版
class Solution {
public int findBlackPixel(char[][] picture, int N) {
if (picture == null || picture.length == 0) {
return 0;
}
int m = picture.length, n = picture.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)