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.
The second condition in the problem is equivalent to requiring that for each column containing black pixels, these rows are exactly the same.
Therefore, we can use an adjacency list g to store all the rows containing black pixels in each column, i.e., g[j] represents the set of all rows containing black pixels in the j-th column. In addition, we use an array rows to store the number of black pixels in each row.
Next, we traverse each column. For each column, we find the first row i_1 containing black pixels. If the number of black pixels in this row is not equal to target, then this column cannot contain lonely pixels, and we skip it directly. Otherwise, we check whether all the rows containing black pixels in this column are exactly the same as the i_1-th row. If so, all the black pixels in this column are lonely pixels, and we add target to the answer.
After the traversal, we return the answer.
The time complexity is O(m times n^2), and the space complexity is O(m times n), where m and n are the number of rows and columns in the matrix respectively.
Python
Java
C++
Go
TypeScript
| 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 |
Leetcode 533 Lonely Pixel II 刷题 & 讲解 • JessieW • 358 views views
Watch 3 more video solutions →Practice Lonely Pixel II with our built-in code editor and test cases.
Practice on FleetCode