Problem

Given an m x n picture consisting of black 'B' and white 'W' pixels, return the number ofblack lonely pixels.

A black lonely pixel is a character 'B' that located at a specific position where the same row and same column don’t have any other black pixels.

Examples

Example 1:

1
2
3
4

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0500-0599/0531.Lonely%20Pixel%20I/images/pixel1.jpg)
Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

Example 2:

1
2
3

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0500-0599/0531.Lonely%20Pixel%20I/images/pixel2.jpg)
Input: picture = [["B","B","B"],["B","B","W"],["B","B","B"]]
Output: 0

Constraints:

  • m == picture.length
  • n == picture[i].length
  • 1 <= m, n <= 500
  • picture[i][j] is 'W' or 'B'.

Solution

Method 1 – Row and Column Counting (1)

Intuition

A black pixel is lonely if it is the only ‘B’ in its row and column. By counting the number of ‘B’s in each row and column, we can efficiently check for lonely pixels.

Approach

  1. Initialize two arrays to count ‘B’s in each row and column.
  2. Traverse the matrix and increment the counts for each ‘B’.
  3. Traverse the matrix again, and for each ‘B’, check if its row and column counts are both 1.
  4. Count such pixels and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& pic) {
        int m = pic.size(), n = pic[0].size();
        vector<int> row(m), col(n);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (pic[i][j] == 'B') row[i]++, col[j]++;
        int ans = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (pic[i][j] == 'B' && row[i] == 1 && col[j] == 1) 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

func findLonelyPixel(pic [][]byte) int {
    m, n := len(pic), len(pic[0])
    row := make([]int, m)
    col := make([]int, n)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pic[i][j] == 'B' {
                row[i]++
                col[j]++
            }
        }
    }
    ans := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if pic[i][j] == 'B' && row[i] == 1 && col[j] == 1 {
                ans++
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int findLonelyPixel(char[][] pic) {
        int m = pic.length, n = pic[0].length;
        int[] row = new int[m], col = new int[n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (pic[i][j] == 'B') { row[i]++; col[j]++; }
        int ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (pic[i][j] == 'B' && row[i] == 1 && col[j] == 1) ans++;
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun findLonelyPixel(pic: Array<CharArray>): Int {
        val m = pic.size
        val n = pic[0].size
        val row = IntArray(m)
        val col = IntArray(n)
        for (i in 0 until m)
            for (j in 0 until n)
                if (pic[i][j] == 'B') { row[i]++; col[j]++ }
        var ans = 0
        for (i in 0 until m)
            for (j in 0 until n)
                if (pic[i][j] == 'B' && row[i] == 1 && col[j] == 1) ans++
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def findLonelyPixel(self, pic: list[list[str]]) -> int:
        m, n = len(pic), len(pic[0])
        row = [0] * m
        col = [0] * n
        for i in range(m):
            for j in range(n):
                if pic[i][j] == 'B':
                    row[i] += 1
                    col[j] += 1
        ans = 0
        for i in range(m):
            for j in range(n):
                if pic[i][j] == 'B' and row[i] == 1 and col[j] == 1:
                    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

impl Solution {
    pub fn find_lonely_pixel(pic: Vec<Vec<char>>) -> i32 {
        let m = pic.len();
        let n = pic[0].len();
        let mut row = vec![0; m];
        let mut col = vec![0; n];
        for i in 0..m {
            for j in 0..n {
                if pic[i][j] == 'B' {
                    row[i] += 1;
                    col[j] += 1;
                }
            }
        }
        let mut ans = 0;
        for i in 0..m {
            for j in 0..n {
                if pic[i][j] == 'B' && row[i] == 1 && col[j] == 1 {
                    ans += 1;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    findLonelyPixel(pic: string[][]): number {
        const m = pic.length, n = pic[0].length;
        const row = Array(m).fill(0), col = Array(n).fill(0);
        for (let i = 0; i < m; i++)
            for (let j = 0; j < n; j++)
                if (pic[i][j] === 'B') { row[i]++; col[j]++; }
        let ans = 0;
        for (let i = 0; i < m; i++)
            for (let j = 0; j < n; j++)
                if (pic[i][j] === 'B' && row[i] === 1 && col[j] === 1) ans++;
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(mn), where m and n are the dimensions of the matrix. We scan the matrix twice.
  • 🧺 Space complexity: O(m+n), for the row and column count arrays.