531. Lonely Pixel I - Explanation

Description

Given an m x n picture consisting of black 'B' and white 'W' pixels, return the number of black 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.

Example 1:

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:

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'.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Counting with Arrays

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        n = len(picture)
        m = len(picture[0])
        
        # Arrays to store the count of black cells in rows and columns.
        row_count = [0] * n
        column_count = [0] * m
        for i in range(n):
            for j in range(m):
                if picture[i][j] == 'B':
                    row_count[i] += 1
                    column_count[j] += 1
        
        answer = 0
        for i in range(n):
            for j in range(m):
                # Its a lonely cell, if the current cell is black and,
                # the count of black cells in its row and column is 1.
                if picture[i][j] == 'B' and row_count[i] == 1 and column_count[j] == 1:
                    answer += 1
        
        return answer

Time & Space Complexity

Time complexity: $O(M \cdot N)$
Space complexity: $O(M + N)$

Where $M$ is the number of rows in the given matrix picture, and $N$ is the number of columns in it.

2. Space Optimized Counting

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        # Returns true if the cell at (x, y) is lonely.
        # There should not be any other black cell 
        # In the first row and column except (x, y) itself.
        def check(x, y):
            n = len(picture)
            m = len(picture[0])
            
            cnt = 0
            for i in range(n):
                cnt += 1 if picture[i][y] == 'B' else 0
            
            for j in range(m):
                # avoid double count (x, y)
                if j != y:
                    cnt += 1 if picture[x][j] == 'B' else 0
            
            return picture[x][y] == 'B' and cnt == 1
        
        n = len(picture)
        m = len(picture[0])
        
        answer = 0
        for j in range(m):
            answer += 1 if check(0, j) else 0
        
        for i in range(1, n):
            answer += 1 if check(i, 0) else 0
        
        # Convert cell 'B' to '1' and 'W' to '0'
        for j in range(m):
            picture[0][j] = '1' if picture[0][j] == 'B' else '0'
        
        for i in range(n):
            picture[i][0] = '1' if picture[i][0] == 'B' else '0'
        
        # If the cell is black increment the count of corresponding row and column by 1
        for i in range(1, n):
            for j in range(1, m):
                if picture[i][j] == 'B':
                    picture[i][0] = chr(ord(picture[i][0]) + 1)
                    picture[0][j] = chr(ord(picture[0][j]) + 1)
        
        for i in range(1, n):
            for j in range(1, m):
                if picture[i][j] == 'B':
                    if picture[0][j] == '1' and picture[i][0] == '1':
                        answer += 1
        
        return answer

Time & Space Complexity

Time complexity: $O(M \cdot N)$
Space complexity: $O(1)$ constant space

Where $M$ is the number of rows in the given matrix picture, and $N$ is the number of columns in it.