Domain 2MediumCORE

Lonely Pixel I

We are given a grid of characters representing pixels, where 'B' denotes black and 'W' denotes white. We need to count how many black pixels qualify as 'lonely.' A pixel is lonely if it is the only black pixel in its specific row AND the only black pixel in its specific column.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array#Depth-first Search

531. Lonely Pixel I

Model: qwen3.5:9b
Topics: Array,Depth-first Search
FAANG asked: 0
Acceptance rate: 59.7%


Problem Breakdown

We are given a grid of characters representing pixels, where 'B' denotes black and 'W' denotes white. We need to count how many black pixels qualify as “lonely.” A pixel is lonely if it is the only black pixel in its specific row AND the only black pixel in its specific column.

  • Inputs: picture: a 2D list of characters (m x n grid).
  • Outputs: An integer representing the count of lonely pixels.
  • Constraints: Grid dimensions up to 500×500500 \times 500. Characters are strictly 'W' or 'B'. No empty input (min dimension is 1).

Intuition

A naive approach would be to iterate through every pixel in the grid. Whenever we encounter a 'B', we scan its entire row and column to see if there are any other 'B's. If not, we increment our counter.

  • Naive Complexity: For each of M×NM \times N pixels (worst case all ‘B’), scanning the row takes O(N)O(N) and the column takes O(M)O(M). Total complexity would be roughly O((MN)(M+N))O((MN)(M+N)), which is approximately 250,000×1,000=2.5×108250,000 \times 1,000 = 2.5 \times 10^8 operations for max constraints. This risks Time Limit Exceeded (TLE).
  • Key Insight: The condition “no other black pixels in row/column” implies we simply need to know the total count of 'B's per row and column beforehand. If a specific cell is 'B', checking if row_count[r] == 1 and col_count[c] == 1 tells us immediately if it satisfies the condition without rescanning lines.

Approach

We will use two passes over the grid to achieve O(MN)O(MN) time complexity:

  1. Precomputation: Initialize two frequency arrays, one for rows (row_counts) and one for columns (col_counts). Iterate through every cell in picture. If a 'B' is found at (r, c), increment both the row count for r and column count for c.
  2. Validation: Iterate through the grid again (or iterate specifically over rows where counts are valid). For each cell that contains a 'B', check if its corresponding entry in our frequency arrays is exactly 1. If so, it’s lonely; increment result counter.

This ensures we traverse the data linearly relative to input size with minimal overhead per element.

Complexity Analysis

  • Time: O(M⋅N)O(M \cdot N). We iterate through the grid twice (once for counting frequencies, once for validation). Since operations inside loops are constant time (O(1)O(1)), total is proportional to number of pixels.
  • Space: O(M+N)O(M + N). We use two auxiliary arrays (row_counts and col_counts) with sizes equal to the grid dimensions.

Solution

class Solution:
    def findLonelyPixel(self, picture):
        if not picture or not picture[0]:
            return 0
        
        m = len(picture)
        n = len(picture[0])
        
        # Precompute counts for each row and column
        row_counts = [0] * m
        col_counts = [0] * n
        
        for r in range(m):
            for c in range(n):
                if picture[r][c] == 'B':
                    row_counts[r] += 1
                    col_counts[c] += 1
                    
        lonely_count = 0
        
        # Check condition: is it a B AND unique in its row/col?
        for r in range(m):
            for c in range(n):
                if picture[r][c] == 'B' and \
                   row_counts[r] == 1 and col_counts[c] == 1:
                    lonely_count += 1
                    
        return lonely_count

Edge Cases Handled

  • All White Pixels: row_counts and col_counts remain all zeros. The condition picture[r][c] == 'B' fails, returning 0 correctly.
  • Single Pixel Grid (e.g., [["W"]] or [["B"]]): If grid is 1x1, counts are 1 if it’s 'B'. Logic holds: row count 1 and col count 1 -> returns 1 for a single black pixel, which matches the definition of “lonely” (no other pixels).
  • All Black Pixels: Every row/col will have count > 1 (unless grid is 1×N1 \times N or M×1M \times 1, but even then counts exceed 1 if multiple exist in line). Returns 0 correctly.