Skip to main content
Talentd

Lonely Pixel II - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableMatrix11 min readAsked at: Google
Practice this problem

Problem Statement

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.

 

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.length
  • n == picture[i].length
  • 1 <= m, n <= 200
  • picture[i][j] is 'W' or 'B'.
  • 1 <= target <= min(m, n)

Approach Overview

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.

Solution

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force ValidationO(m^2 * n)O(1)Useful for understanding constraints or when grid size is very small
Counting with Row Pattern HashingO(m * n)O(m * n)General case and interview-preferred solution for large matrices

Video Solution

Leetcode 533 Lonely Pixel II 刷题 & 讲解 • JessieW • 359 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Lonely Pixel II easy or hard?
Lonely Pixel II is considered a medium difficulty problem. The main challenge is recognizing that identical rows can be grouped using hashing to avoid expensive row comparisons, reducing the complexity from quadratic to linear with respect to the matrix size.
Lonely Pixel II Python/Java solution
Most implementations follow the same logic across languages: convert rows to strings, store frequencies in a dictionary or map, count black pixels per column, and validate candidate rows. Python uses a dictionary, while Java typically uses HashMap<String, Integer>.
How to solve Lonely Pixel II in O(m*n)?
First convert every row into a string and store its frequency in a hash map. Maintain an array counting black pixels for each column. For every row pattern that appears exactly N times and contains exactly N black pixels, check each column with 'B'. If that column also has N black pixels, add N to the answer.
What is the best approach for Lonely Pixel II?
The most efficient solution uses counting with a hash map of row patterns. Count how many times each row appears and track the number of black pixels per column. If a row contains exactly N black pixels and appears N times, then each column with a black pixel and column count N contributes N valid pixels. This runs in O(m*n) time.
Is Lonely Pixel II asked at Google/Amazon/Meta?
Matrix counting and hash-map based pattern problems similar to Lonely Pixel II appear in interviews at companies like Amazon, Google, and Meta. The problem tests grid traversal, hashing, and recognizing repeated patterns for optimization.
What data structure is used in Lonely Pixel II?
The optimal solution uses a hash map to store row patterns and their frequencies, along with arrays for column counts. These structures allow constant-time lookups and avoid repeated row comparisons across the matrix.
What is the time complexity of Lonely Pixel II?
The optimal approach runs in O(m*n) time where m is the number of rows and n is the number of columns. Each cell is processed during row pattern creation and column counting. Hash map lookups and column checks remain constant time.

Ready to solve this problem?

Practice Lonely Pixel II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Lonely Pixel I