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 ngrid). - Outputs: An integer representing the count of lonely pixels.
- Constraints: Grid dimensions up to . 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 pixels (worst case all ‘B’), scanning the row takes and the column takes . Total complexity would be roughly , which is approximately 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'sper row and column beforehand. If a specific cell is'B', checking ifrow_count[r] == 1andcol_count[c] == 1tells us immediately if it satisfies the condition without rescanning lines.
Approach
We will use two passes over the grid to achieve time complexity:
- Precomputation: Initialize two frequency arrays, one for rows (
row_counts) and one for columns (col_counts). Iterate through every cell inpicture. If a'B'is found at(r, c), increment both the row count forrand column count forc. - 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 exactly1. 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: . We iterate through the grid twice (once for counting frequencies, once for validation). Since operations inside loops are constant time (), total is proportional to number of pixels.
- Space: . We use two auxiliary arrays (
row_countsandcol_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_countsandcol_countsremain all zeros. The conditionpicture[r][c] == 'B'fails, returning 0 correctly. - Single Pixel Grid (e.g.,
[["W"]]or[["B"]]): If grid is1x1, 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 or , but even then counts exceed 1 if multiple exist in line). Returns 0 correctly.