Lonely Pixel II
MediumUpdated: Aug 2, 2025
Practice on:
Problem
Given an m x n picture consisting of black 'B' and white 'W' pixels and an integer target, return the number ofblack lonely pixels.
A black lonely pixel is a character 'B' that located at a specific position
(r, c) where:
- Row
rand columncboth contain exactlytargetblack pixels. - For all rows that have a black pixel at column
c, they should be exactly the same as rowr.
Examples
Example 1:
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"]], target = 3
Output: 6
Explanation: All the green 'B' are the black pixels we need (all 'B's at column 1 and 3).
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 target = 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.
Example 2:
Input: picture = [["W","W","B"],["W","W","B"],["W","W","B"]], target = 1
Output: 0
Constraints:
m == picture.lengthn == picture[i].length1 <= m, n <= 200picture[i][j]is'W'or'B'.1 <= target <= min(m, n)
Solution
Method 1 – Hashing and Row Pattern Counting (1)
Intuition
A black pixel at (r, c) is lonely if both its row and column have exactly target black pixels, and all rows with a black pixel in column c are identical to row r. We can use hashing to count row patterns and check columns efficiently.
Approach
- For each row, count the number of 'B's and store the row as a string pattern.
- For each column, count the number of 'B's and record which rows have a 'B' in that column.
- For each row pattern that appears exactly
targettimes, for each column where that row has a 'B', check if:- The column has exactly
target'B's. - All rows with a 'B' in that column match the current row pattern.
- The column has exactly
- For each such valid (row, col), add
targetto the answer (since each such column will contributetargetlonely pixels).
Code
C++
class Solution {
public:
int findBlackPixel(vector<vector<char>>& pic, int target) {
int m = pic.size(), n = pic[0].size();
unordered_map<string, int> rowMap;
vector<int> colCnt(n, 0);
vector<string> rows(m);
for (int i = 0; i < m; ++i) {
string s(pic[i].begin(), pic[i].end());
rows[i] = s;
rowMap[s]++;
for (int j = 0; j < n; ++j)
if (pic[i][j] == 'B') colCnt[j]++;
}
int ans = 0;
for (int i = 0; i < m; ++i) {
if (count(rows[i].begin(), rows[i].end(), 'B') != target) continue;
if (rowMap[rows[i]] != target) continue;
for (int j = 0; j < n; ++j) {
if (pic[i][j] == 'B' && colCnt[j] == target) {
bool valid = true;
for (int k = 0; k < m; ++k) {
if (pic[k][j] == 'B' && rows[k] != rows[i]) {
valid = false;
break;
}
}
if (valid) ans++;
}
}
}
return ans;
}
};
Go
func findBlackPixel(pic [][]byte, target int) int {
m, n := len(pic), len(pic[0])
rowMap := map[string]int{}
colCnt := make([]int, n)
rows := make([]string, m)
for i := 0; i < m; i++ {
s := string(pic[i])
rows[i] = s
rowMap[s]++
for j := 0; j < n; j++ {
if pic[i][j] == 'B' {
colCnt[j]++
}
}
}
ans := 0
for i := 0; i < m; i++ {
cnt := 0
for _, c := range rows[i] {
if c == 'B' {
cnt++
}
}
if cnt != target || rowMap[rows[i]] != target {
continue
}
for j := 0; j < n; j++ {
if pic[i][j] == 'B' && colCnt[j] == target {
valid := true
for k := 0; k < m; k++ {
if pic[k][j] == 'B' && rows[k] != rows[i] {
valid = false
break
}
}
if valid {
ans++
}
}
}
}
return ans
}
Java
class Solution {
public int findBlackPixel(char[][] pic, int target) {
int m = pic.length, n = pic[0].length;
Map<String, Integer> rowMap = new HashMap<>();
int[] colCnt = new int[n];
String[] rows = new String[m];
for (int i = 0; i < m; i++) {
String s = new String(pic[i]);
rows[i] = s;
rowMap.put(s, rowMap.getOrDefault(s, 0) + 1);
for (int j = 0; j < n; j++)
if (pic[i][j] == 'B') colCnt[j]++;
}
int ans = 0;
for (int i = 0; i < m; i++) {
if (rows[i].chars().filter(c -> c == 'B').count() != target) continue;
if (rowMap.get(rows[i]) != target) continue;
for (int j = 0; j < n; j++) {
if (pic[i][j] == 'B' && colCnt[j] == target) {
boolean valid = true;
for (int k = 0; k < m; k++) {
if (pic[k][j] == 'B' && !rows[k].equals(rows[i])) {
valid = false;
break;
}
}
if (valid) ans++;
}
}
}
return ans;
}
}
Kotlin
class Solution {
fun findBlackPixel(pic: Array<CharArray>, target: Int): Int {
val m = pic.size
val n = pic[0].size
val rowMap = mutableMapOf<String, Int>()
val colCnt = IntArray(n)
val rows = Array(m) { String(pic[it]) }
for (i in 0 until m) {
rowMap[rows[i]] = rowMap.getOrDefault(rows[i], 0) + 1
for (j in 0 until n) if (pic[i][j] == 'B') colCnt[j]++
}
var ans = 0
for (i in 0 until m) {
if (rows[i].count { it == 'B' } != target) continue
if (rowMap[rows[i]] != target) continue
for (j in 0 until n) {
if (pic[i][j] == 'B' && colCnt[j] == target) {
var valid = true
for (k in 0 until m) {
if (pic[k][j] == 'B' && rows[k] != rows[i]) {
valid = false
break
}
}
if (valid) ans++
}
}
}
return ans
}
}
Python
class Solution:
def findBlackPixel(self, pic: list[list[str]], target: int) -> int:
m, n = len(pic), len(pic[0])
row_map: dict[str, int] = {}
col_cnt = [0] * n
rows = [''.join(pic[i]) for i in range(m)]
for i in range(m):
row_map[rows[i]] = row_map.get(rows[i], 0) + 1
for j in range(n):
if pic[i][j] == 'B':
col_cnt[j] += 1
ans = 0
for i in range(m):
if rows[i].count('B') != target or row_map[rows[i]] != target:
continue
for j in range(n):
if pic[i][j] == 'B' and col_cnt[j] == target:
if all(rows[k] == rows[i] for k in range(m) if pic[k][j] == 'B'):
ans += 1
return ans
Rust
impl Solution {
pub fn find_black_pixel(pic: Vec<Vec<char>>, target: i32) -> i32 {
let m = pic.len();
let n = pic[0].len();
use std::collections::HashMap;
let mut row_map = HashMap::new();
let mut col_cnt = vec![0; n];
let mut rows = vec![String::new(); m];
for i in 0..m {
rows[i] = pic[i].iter().collect();
*row_map.entry(rows[i].clone()).or_insert(0) += 1;
for j in 0..n {
if pic[i][j] == 'B' {
col_cnt[j] += 1;
}
}
}
let mut ans = 0;
for i in 0..m {
if rows[i].chars().filter(|&c| c == 'B').count() as i32 != target || *row_map.get(&rows[i]).unwrap() != target {
continue;
}
for j in 0..n {
if pic[i][j] == 'B' && col_cnt[j] == target {
if (0..m).all(|k| pic[k][j] != 'B' || rows[k] == rows[i]) {
ans += 1;
}
}
}
}
ans
}
}
TypeScript
class Solution {
findBlackPixel(pic: string[][], target: number): number {
const m = pic.length, n = pic[0].length;
const rowMap = new Map<string, number>();
const colCnt = Array(n).fill(0);
const rows = pic.map(row => row.join(''));
for (let i = 0; i < m; i++) {
rowMap.set(rows[i], (rowMap.get(rows[i]) || 0) + 1);
for (let j = 0; j < n; j++)
if (pic[i][j] === 'B') colCnt[j]++;
}
let ans = 0;
for (let i = 0; i < m; i++) {
if ((rows[i].split('B').length - 1) !== target || rowMap.get(rows[i]) !== target) continue;
for (let j = 0; j < n; j++) {
if (pic[i][j] === 'B' && colCnt[j] === target) {
let valid = true;
for (let k = 0; k < m; k++) {
if (pic[k][j] === 'B' && rows[k] !== rows[i]) {
valid = false;
break;
}
}
if (valid) ans++;
}
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(mn^2), where m and n are the dimensions of the matrix. For each row and column, we may scan all rows. - 🧺 Space complexity:
O(mn), for storing row patterns and counts.