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.

Description Solution Video 14:00

531. Lonely Pixel I

Medium62.3% acceptance1 companyPremium elsewhere, free here

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'.

Asked at 1 company

Google

Topics

14:00

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

531. Lonely Pixel I

Asked at 1 company

Topics

Similar problems