Problem Description

You are given an m x n grid called picture where each cell contains either a black pixel represented by 'B' or a white pixel represented by 'W'.

A black lonely pixel is defined as a black pixel 'B' that satisfies the following condition: there are no other black pixels in the same row AND no other black pixels in the same column (the pixel itself doesn't count against this condition).

Your task is to count and return the total number of black lonely pixels in the entire picture.

For example, if a black pixel is located at position (i, j), it is considered "lonely" only if:

• Row i contains exactly one black pixel (the one at position (i, j))
• Column j contains exactly one black pixel (the one at position (i, j))

The solution works by first counting the total number of black pixels in each row and column using two arrays rows and cols. Then it traverses through the picture again, and for each black pixel, checks if its row count and column count are both equal to 1. If both conditions are met, that pixel is lonely and contributes to the answer.

Intuition

The key insight is that a lonely black pixel must be the only black pixel in both its row and column. Instead of checking every other position in the same row and column for each black pixel (which would be inefficient), we can preprocess the information we need.

Think of it this way: if we know in advance how many black pixels exist in each row and each column, we can quickly determine if a black pixel is lonely. A black pixel at position (i, j) is lonely if and only if:

• Row i has exactly 1 black pixel total
• Column j has exactly 1 black pixel total

This leads us to a two-pass approach:

First pass: Count the occurrences. We traverse the entire grid once and maintain two counting arrays:

• rows[i] = number of black pixels in row i
• cols[j] = number of black pixels in column j

Second pass: Identify lonely pixels. We traverse the grid again, and for each black pixel at (i, j), we check if rows[i] == 1 and cols[j] == 1. If both conditions are true, this black pixel is the only one in its row and column, making it lonely.

This approach transforms the problem from "checking isolation for each pixel" to "counting and verification", reducing the time complexity from O(m*n*(m+n)) to O(m*n).

Solution Approach

The solution uses a counting approach with enumeration to efficiently identify lonely black pixels.

Step 1: Initialize Counting Arrays

We create two arrays to track black pixel counts:

• rows = [0] * len(picture) - stores the count of black pixels in each row
• cols = [0] * len(picture[0]) - stores the count of black pixels in each column

Step 2: First Pass - Count Black Pixels

We iterate through the entire picture using nested loops:

for i, row in enumerate(picture):
    for j, x in enumerate(row):
        if x == "B":
            rows[i] += 1
            cols[j] += 1

For each black pixel found at position (i, j), we increment both rows[i] and cols[j]. After this pass, we have complete information about the distribution of black pixels across all rows and columns.

Step 3: Second Pass - Find Lonely Pixels

We traverse the picture again with the same nested loop structure:

ans = 0
for i, row in enumerate(picture):
    for j, x in enumerate(row):
        if x == "B" and rows[i] == 1 and cols[j] == 1:
            ans += 1

For each position (i, j), we check three conditions:

1. The pixel is black (x == "B")
2. Its row has exactly one black pixel (rows[i] == 1)
3. Its column has exactly one black pixel (cols[j] == 1)

If all three conditions are met, the pixel is lonely, and we increment our answer counter.

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns. We traverse the grid twice.

Space Complexity: O(m + n) for storing the row and column count arrays.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×4 grid:

picture = [
  ["W", "W", "B", "W"],
  ["W", "B", "W", "B"],
  ["B", "W", "W", "W"]
]

Step 1: Initialize Counting Arrays

• rows = [0, 0, 0] (one counter for each of the 3 rows)
• cols = [0, 0, 0, 0] (one counter for each of the 4 columns)

Step 2: First Pass - Count Black Pixels

We traverse each cell and count black pixels:

• Position (0,2): Found 'B' → rows[0] = 1, cols[2] = 1
• Position (1,1): Found 'B' → rows[1] = 1, cols[1] = 1
• Position (1,3): Found 'B' → rows[1] = 2, cols[3] = 1
• Position (2,0): Found 'B' → rows[2] = 1, cols[0] = 1

After the first pass:

• rows = [1, 2, 1] (row 0 has 1 black, row 1 has 2 blacks, row 2 has 1 black)
• cols = [1, 1, 1, 1] (each column has exactly 1 black pixel)

Step 3: Second Pass - Find Lonely Pixels

Now we check each black pixel to see if it's lonely:

• Position (0,2): 'B' with rows[0] = 1 and cols[2] = 1 → Lonely! (ans = 1)
• Position (1,1): 'B' with rows[1] = 2 and cols[1] = 1 → Not lonely (row has 2 blacks)
• Position (1,3): 'B' with rows[1] = 2 and cols[3] = 1 → Not lonely (row has 2 blacks)
• Position (2,0): 'B' with rows[2] = 1 and cols[0] = 1 → Lonely! (ans = 2)

Result: The function returns 2, as there are exactly 2 lonely black pixels at positions (0,2) and (2,0).

Notice how the pixels at (1,1) and (1,3) are not lonely because they share row 1, even though each is the only black pixel in its respective column.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two main phases:

1. First traversal through the entire matrix to count the number of 'B' pixels in each row and column - this takes O(m × n) time where we visit each cell exactly once.
2. Second traversal through the entire matrix to identify lonely pixels (pixels where both rows[i] == 1 and cols[j] == 1) - this also takes O(m × n) time.

Since both traversals are sequential and not nested, the total time complexity is O(m × n) + O(m × n) = O(m × n), where m is the number of rows and n is the number of columns in the picture matrix.

Space Complexity: O(m + n)

The algorithm uses two auxiliary arrays:

• rows array of size m to store the count of 'B' pixels in each row
• cols array of size n to store the count of 'B' pixels in each column

The total extra space used is O(m) + O(n) = O(m + n), where m is the number of rows and n is the number of columns in the picture matrix.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the "Lonely" Definition

A common mistake is thinking that a black pixel is lonely if there are no other black pixels adjacent to it (in the 4 or 8 directions), rather than checking the entire row and column. The problem specifically requires checking the entire row and column, not just neighboring cells.

Incorrect Understanding:

# WRONG: Checking only adjacent cells
def isLonely(picture, i, j):
    directions = [(0,1), (1,0), (0,-1), (-1,0)]
    for di, dj in directions:
        ni, nj = i + di, j + dj
        if 0 <= ni < len(picture) and 0 <= nj < len(picture[0]):
            if picture[ni][nj] == "B":
                return False
    return True

Correct Approach: The pixel must be the only black pixel in its entire row AND entire column.

2. Off-by-One Errors in Counting

Some implementations might incorrectly check if the count equals 0 instead of 1, forgetting that the pixel itself contributes to the count.

Incorrect:

# WRONG: Checking for 0 instead of 1
if picture[i][j] == "B" and row_counts[i] == 0 and col_counts[j] == 0:
    lonely_pixel_count += 1

Correct:

# The lonely pixel itself contributes 1 to both counts
if picture[i][j] == "B" and row_counts[i] == 1 and col_counts[j] == 1:
    lonely_pixel_count += 1

3. Single Pass Attempt

Trying to identify lonely pixels in a single pass can lead to incorrect results because you need complete row and column counts before determining if a pixel is lonely.

Incorrect Single Pass:

# WRONG: Can't determine loneliness without complete counts
lonely_count = 0
for i in range(m):
    for j in range(n):
        if picture[i][j] == "B":
            # Can't know if this is the only one yet!
            if isOnlyInRowAndCol(picture, i, j):  
                lonely_count += 1

Solution: Use two passes - first to count all black pixels in rows and columns, second to identify lonely pixels based on complete counts.

4. Inefficient Row/Column Checking

Checking the entire row and column for each black pixel individually leads to O(m²n + mn²) time complexity.

Inefficient:

def countLonelyPixels(picture):
    count = 0
    for i in range(len(picture)):
        for j in range(len(picture[0])):
            if picture[i][j] == "B":
                # O(m+n) check for each black pixel
                row_blacks = sum(1 for cell in picture[i] if cell == "B")
                col_blacks = sum(1 for row in picture if row[j] == "B")
                if row_blacks == 1 and col_blacks == 1:
                    count += 1
    return count

Efficient Solution: Pre-compute all row and column counts in O(mn) time, then check in O(1) time per pixel.