Skip to main content
Talentd

Lonely Pixel I - Solution & Explanation

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

Problem Statement

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

A black lonely pixel is a character 'B' that located at a specific position where the same row and same column don't have any other black pixels.

 

Example 1:

Input: picture = [["W","W","B"],["W","B","W"],["B","W","W"]]
Output: 3
Explanation: All the three 'B's are black lonely pixels.

Example 2:

Input: picture = [["B","B","B"],["B","B","W"],["B","B","B"]]
Output: 0

 

Constraints:

  • m == picture.length
  • n == picture[i].length
  • 1 <= m, n <= 500
  • picture[i][j] is 'W' or 'B'.

Approach Overview

Problem Overview: You are given a 2D picture containing characters 'B' (black) and 'W' (white). A black pixel is considered lonely if it is the only black pixel in its row and its column. The task is to count how many such pixels exist in the matrix.

Approach 1: Brute Force Row and Column Scan (O(mn(m+n)) time, O(1) space)

Iterate through every cell in the matrix. When you encounter a 'B', scan the entire row and entire column to check if any other 'B' exists. If both the row and column contain exactly one black pixel, increment the result. This approach performs repeated row and column scans for each candidate pixel, which increases the total work significantly. It is straightforward and useful for validating correctness but inefficient for larger matrices.

Approach 2: Counting + Enumeration (O(mn) time, O(m+n) space)

Precompute the number of black pixels in each row and each column. Create two arrays: rowCount[m] and colCount[n]. First pass: iterate through the matrix and increment the corresponding row and column counters whenever you see 'B'. Second pass: iterate again and check each 'B'. If rowCount[i] == 1 and colCount[j] == 1, that pixel is lonely and contributes to the answer.

The key insight is that loneliness depends only on counts, not positions of other pixels. Precomputing these counts avoids repeated scans and reduces the complexity to a single linear pass over the grid plus a verification pass. This pattern appears frequently in matrix problems where row and column statistics are reused.

The implementation uses simple arrays or hash maps depending on the language. In most cases arrays are enough because indices correspond directly to rows and columns. The logic is deterministic: count first, then enumerate candidates. This is a common counting trick used in problems involving grids, frequency tracking, or uniqueness checks in array and hash table style problems.

Recommended for interviews: Counting + Enumeration. Interviewers expect you to avoid repeated row/column scans and instead store counts. The brute force approach demonstrates understanding of the condition, but the optimized counting method shows you can reduce redundant work and reach the optimal O(mn) solution.

Solution

According to the problem description, we need to count the number of black pixels in each row and column, which are recorded in the arrays rows and cols respectively. Then we traverse each black pixel, check whether there is only one black pixel in its row and column. If so, we increment the answer by one.

The time complexity is O(m times n), and the space complexity is O(m + 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 Row & Column ScanO(mn(m+n))O(1)When first reasoning about the problem or validating correctness on small grids
Counting + EnumerationO(mn)O(m+n)General optimal solution for interview and production scenarios

Video Solution

531 - Lonely Pixel I (LeetCode) • Programmer Fellas • 230 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Lonely Pixel I easy or hard?
Lonely Pixel I is generally considered a medium-level problem. The logic is simple once you recognize that repeated row and column scans are unnecessary. The main skill tested is recognizing that precomputing row and column counts reduces the complexity to O(mn).
Lonely Pixel I Python/Java solution
In Python or Java, create two arrays sized by the number of rows and columns. Iterate through the matrix to count 'B' occurrences per row and column, then iterate again to check if both counts equal 1 for each 'B'. This implementation runs in O(mn) time and is the standard interview solution.
How to solve Lonely Pixel I in O(n)?
Treat the matrix dimensions as m x n and process every cell once. Maintain two arrays: rowCount and colCount. During the first pass count how many 'B' pixels appear in each row and column, then during the second pass check if rowCount[i] == 1 and colCount[j] == 1 for a 'B'. This reduces redundant scanning and achieves O(mn) time.
What is the best approach for Lonely Pixel I?
The optimal approach is Counting + Enumeration. First count how many black pixels appear in each row and column using two arrays. Then iterate through the matrix again and count cells where the value is 'B' and both the row and column counts equal 1. This runs in O(mn) time with O(m+n) extra space.
Is Lonely Pixel I asked at Google/Amazon/Meta?
Lonely Pixel I represents a classic matrix counting problem and has appeared in interview preparation sets used by companies such as Amazon and Google. Variants that involve row/column frequency constraints are common in technical interviews because they test grid traversal and counting optimizations.
What data structure is used in Lonely Pixel I?
The solution mainly uses arrays (or hash tables) to store row and column frequencies. Two counters track how many black pixels appear per row and per column. The matrix itself is traversed twice to compute counts and then verify lonely pixels.
What is the time complexity of Lonely Pixel I?
The optimal solution runs in O(mn) time where m is the number of rows and n is the number of columns. You scan the matrix once to build row and column counts and a second time to verify lonely pixels. Space complexity is O(m+n) for storing row and column frequencies.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Lonely Pixel II