Watch 4 video solutions for Lonely Pixel II, a medium level problem involving Array, Hash Table, Matrix. This walkthrough by JessieW has 358 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
r and column c both contain exactly target black pixels.c, they should be exactly the same as row r.
Example 1:
Input: picture = [["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","B","W","B","B","W"],["W","W","B","W","B","W"]], target = 3 Output: 6 Explanation: All the green 'B' are the black pixels we need (all 'B's at column 1 and 3). Take 'B' at row r = 0 and column c = 1 as an example: - Rule 1, row r = 0 and column c = 1 both have exactly target = 3 black pixels. - Rule 2, the rows have black pixel at column c = 1 are row 0, row 1 and row 2. They are exactly the same as row r = 0.
Example 2:
Input: picture = [["W","W","B"],["W","W","B"],["W","W","B"]], target = 1 Output: 0
Constraints:
m == picture.lengthn == picture[i].length1 <= m, n <= 200picture[i][j] is 'W' or 'B'.1 <= target <= min(m, n)Problem Overview: You receive a m x n grid containing 'B' (black) and 'W' (white) pixels and an integer N. A pixel at (r, c) is valid if row r has exactly N black pixels, column c has exactly N black pixels, and every row that has a black pixel in column c is identical to row r. The task is to count how many such pixels exist.
Approach 1: Brute Force Validation (O(m^2 * n), Space O(1))
Start by iterating through every cell in the grid. When you encounter a black pixel, compute the number of black pixels in its row and column. If both counts equal N, check every other row that has a black pixel in that column and compare it character by character with the current row. If any row differs, the pixel is invalid. This approach repeatedly scans rows and columns, which leads to O(m^2 * n) time in the worst case.
Approach 2: Counting with Row Pattern Hashing (O(m * n), Space O(m * n))
A more efficient strategy counts row patterns and column black pixels first. Convert each row into a string and store its frequency in a hash map. At the same time, maintain an array that counts how many black pixels appear in each column. Next, iterate through each unique row pattern. If the row contains exactly N black pixels and appears exactly N times, it becomes a candidate row. For every column j where this row has a 'B', check whether the column also contains exactly N black pixels. Each such column contributes N valid pixels because the identical rows guarantee the condition about matching rows. This reduces redundant comparisons and processes the grid in linear time relative to its size.
The key insight is treating rows as patterns. If a row with exactly N black pixels appears N times, and a column aligned with those black pixels also has N blacks, the row-equality condition automatically holds. Hashing row strings avoids expensive pairwise row comparisons.
Recommended for interviews: The counting + hashing approach is the expected solution. Interviewers want to see that you recognize repeated row patterns and replace repeated comparisons with a hash map. Explaining the brute force first shows understanding of the constraints, then optimizing with counting demonstrates strong problem-solving skills using array, hash table, and matrix techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Validation | O(m^2 * n) | O(1) | Useful for understanding constraints or when grid size is very small |
| Counting with Row Pattern Hashing | O(m * n) | O(m * n) | General case and interview-preferred solution for large matrices |