Lonely Pixel II - Practice Coding Problems

Lonely Pixel II - Problem

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

A black lonely pixel is a character 'B' that located at a specific position (r, c) where:

Row r and column c both contain exactly target black pixels.
For all rows that have a black pixel at column c, they should be exactly the same as row r.

Input & Output

Example 1 — Basic Case

$ Input: picture = [["W","B","W"],["B","W","B"],["W","B","W"]], target = 2

› Output: 2

💡 Note: Row 1 has 2 black pixels and columns 0,2 each have 2 black pixels. All rows with black pixels in columns 0,2 are identical to row 1.

Example 2 — No Lonely Pixels

$ Input: picture = [["W","B"],["B","W"]], target = 1

› Output: 0

💡 Note: Each black pixel's row and column have exactly 1 black pixel, but rows 0 and 1 are different, violating the identical row condition.

Example 3 — All Qualify

$ Input: picture = [["B","B"],["B","B"]], target = 2

› Output: 4

💡 Note: All rows are identical with 2 black pixels each, and all columns have 2 black pixels each.

Constraints

1 ≤ m, n ≤ 200
1 ≤ target ≤ min(m, n)
picture[i][j] is either 'W' or 'B'

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Black and white pixel matrix with target count

Check Conditions

Row count, column count, and identical row requirements

Count Result

Number of black pixels satisfying all conditions

Key Takeaway

🎯 Key Insight: Group identical rows to efficiently validate the 'same row' condition for all pixels in a column

Asked in

G Google 15 f Facebook 8 M Microsoft 5

The key insight is to group identical rows together and validate the three conditions efficiently. The optimal approach uses hash maps to group rows by signature and precompute counts. Best approach is optimized row grouping. Time: O(m × n), Space: O(m × n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass with Hash Maps	O(m × n)	O(m + n)	First pass counts pixels, second pass validates conditions with hash maps
Brute Force	O(m² × n²)	O(1)	Check each black pixel against all conditions individually
Optimized Row Grouping	O(m × n)	O(m × n)	Group identical rows first, then validate only qualifying rows efficiently

Two Pass with Hash Maps — Algorithm Steps

First pass: count black pixels per row/column and group identical rows
Second pass: for each black pixel, check conditions using hash maps
Use row signatures to quickly verify identical row requirement

Visualization

Tap to expand

Step-by-Step Walkthrough

First Pass

Count black pixels per row/column, create row signatures

Hash Maps

Store counts and grouped identical rows

Second Pass

Check conditions using precomputed data

Code -

solution.c — C

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Two passes through the matrix, plus hash map operations which are O(1) average

✓ Linear Growth

Space Complexity

O(m + n)

Hash maps store row/column counts and row signatures

⚡ Linearithmic Space

12.4K Views

Medium Frequency

~25 min Avg. Time

485 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pass with Hash Maps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler