Given a 2D array picture representing a black-and-white image, each element is either 'B' (black pixel) or 'W' (white pixel). A black pixel at location picture[i][j] is called a lonely pixel if:
i and column j both contain exactly N black pixels.j are exactly the same as row i.N.
At first glance, we might consider checking each black pixel in the matrix and verifying the two conditions directly. For each black pixel, we could count the number of black pixels in its row and column, and then compare all relevant rows for equality. However, this brute-force method would be inefficient, especially for large matrices.
To optimize, we must avoid redundant checks and repeated row comparisons. We can use hash maps to efficiently count rows and columns and to quickly check if rows are identical. By grouping identical rows and tracking black pixel counts, we can reduce unnecessary work and make the solution scalable.
We can break the solution into several clear steps:
This approach ensures we only consider rows and columns that could possibly meet the conditions, and we use hash maps for efficient lookups and grouping.
Example Input:
picture = [
['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
Step-by-step:
Output: 6
Brute-force Approach:
The optimized solution is linear in the size of the matrix, making it efficient for large inputs.
We solved the Lonely Pixel II problem by grouping identical rows, counting black pixels in both rows and columns, and validating only those rows and columns that meet all conditions. Using hash maps for grouping and counting made the solution efficient and easy to understand. The key insight was to leverage the fact that all candidate rows must be identical, and that we can process the problem with a few passes over the data, leading to an elegant and scalable solution.
class Solution:
def findBlackPixel(self, picture: List[List[str]], N: int) -> int:
from collections import Counter, defaultdict
rows = [''.join(row) for row in picture]
row_count = Counter(rows)
m, n = len(picture), len(picture[0])
col_count = [0] * n
for i in range(m):
for j in range(n):
if picture[i][j] == 'B':
col_count[j] += 1
res = 0
for row_str, count in row_count.items():
if count != N:
continue
idxs = [j for j, ch in enumerate(row_str) if ch == 'B']
if len(idxs) != N:
continue
for j in idxs:
if col_count[j] == N:
# Check all rows with 'B' in column j are the same as this row
valid = True
for i in range(m):
if picture[i][j] == 'B' and ''.join(picture[i]) != row_str:
valid = False
break
if valid:
res += N
return res
class Solution {
public:
int findBlackPixel(vector<vector<char>>& picture, int N) {
int m = picture.size(), n = picture[0].size();
vector<int> colCount(n, 0);
unordered_map<string, int> rowMap;
vector<string> rows(m);
for (int i = 0; i < m; ++i) {
string s(picture[i].begin(), picture[i].end());
rows[i] = s;
rowMap[s]++;
for (int j = 0; j < n; ++j) {
if (picture[i][j] == 'B') colCount[j]++;
}
}
int res = 0;
for (auto &kv : rowMap) {
string rowStr = kv.first;
int count = kv.second;
if (count != N) continue;
vector<int> idxs;
for (int j = 0; j < n; ++j) {
if (rowStr[j] == 'B') idxs.push_back(j);
}
if (idxs.size() != N) continue;
for (int idx : idxs) {
if (colCount[idx] == N) {
bool valid = true;
for (int i = 0; i < m; ++i) {
if (picture[i][idx] == 'B' && rows[i] != rowStr) {
valid = false;
break;
}
}
if (valid) res += N;
}
}
}
return res;
}
};
class Solution {
public int findBlackPixel(char[][] picture, int N) {
int m = picture.length, n = picture[0].length;
int[] colCount = new int[n];
Map<String, Integer> rowMap = new HashMap<>();
String[] rows = new String[m];
for (int i = 0; i < m; ++i) {
StringBuilder sb = new StringBuilder();
for (int j = 0; j < n; ++j) {
sb.append(picture[i][j]);
if (picture[i][j] == 'B') colCount[j]++;
}
rows[i] = sb.toString();
rowMap.put(rows[i], rowMap.getOrDefault(rows[i], 0) + 1);
}
int res = 0;
for (String rowStr : rowMap.keySet()) {
int count = rowMap.get(rowStr);
if (count != N) continue;
List<Integer> idxs = new ArrayList<>();
for (int j = 0; j < n; ++j) {
if (rowStr.charAt(j) == 'B') idxs.add(j);
}
if (idxs.size() != N) continue;
for (int idx : idxs) {
if (colCount[idx] == N) {
boolean valid = true;
for (int i = 0; i < m; ++i) {
if (picture[i][idx] == 'B' && !rows[i].equals(rowStr)) {
valid = false;
break;
}
}
if (valid) res += N;
}
}
}
return res;
}
}
var findBlackPixel = function(picture, N) {
const m = picture.length, n = picture[0].length;
const colCount = Array(n).fill(0);
const rowMap = new Map();
const rows = [];
for (let i = 0; i < m; ++i) {
let rowStr = picture[i].join('');
rows.push(rowStr);
rowMap.set(rowStr, (rowMap.get(rowStr) || 0) + 1);
for (let j = 0; j < n; ++j) {
if (picture[i][j] === 'B') colCount[j]++;
}
}
let res = 0;
for (let [rowStr, count] of rowMap.entries()) {
if (count !== N) continue;
let idxs = [];
for (let j = 0; j < n; ++j) {
if (rowStr[j] === 'B') idxs.push(j);
}
if (idxs.length !== N) continue;
for (let idx of idxs) {
if (colCount[idx] === N) {
let valid = true;
for (let i = 0; i < m; ++i) {
if (picture[i][idx] === 'B' && rows[i] !== rowStr) {
valid = false;
break;
}
}
if (valid) res += N;
}
}
}
return res;
};