Lonely Pixel II

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 r and column c both contain exactly target black pixels.
For all rows that have a black pixel at column c, they should be exactly the same as row r.

Examples

Example 1:

1
2
3
4
5
6
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:

1
2
Input: picture = [["W","W","B"],["W","W","B"],["W","W","B"]], target = 1
Output: 0

Constraints:

m == picture.length
n == picture[i].length
1 <= m, n <= 200
picture[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 target times, 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.
For each such valid (row, col), add target to the answer (since each such column will contribute target lonely pixels).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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.

Problem#

Examples#

Solution#

Method 1 – Hashing and Row Pattern Counting (1)#

Intuition#

Approach#

Code#

Complexity#