Lonely Pixel I - Practice Coding Problems

Lonely Pixel I - Problem

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 is located at a specific position where the same row and same column don't have any other black pixels.

Input & Output

Example 1 — Basic Case

$ Input: picture = [["W","W","B"],["W","B","W"],["W","W","B"]]

› Output: 1

💡 Note: Only the black pixel at (1,1) is lonely. Row 1 has 1 black pixel, column 1 has 1 black pixel. The other black pixels have companions in their rows or columns.

Example 2 — No Lonely Pixels

$ Input: picture = [["B","B"],["B","W"]]

› Output: 0

💡 Note: No lonely pixels exist. The black pixel at (0,0) shares row 0 with (0,1), pixel at (0,1) shares both row 0 and column 1, and pixel at (1,0) shares column 0.

Example 3 — Single Black Pixel

$ Input: picture = [["W","W"],["W","B"]]

› Output: 1

💡 Note: The single black pixel at (1,1) is lonely since it's the only black pixel in both row 1 and column 1.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Grid with 'B' (black) and 'W' (white) pixels

Check Loneliness

For each 'B', verify no other 'B' in same row/column

Count Result

Number of lonely black pixels found

Key Takeaway

🎯 Key Insight: A pixel is lonely only if it's the sole black pixel in both its row and column

Asked in

G Google 15 f Facebook 12 M Microsoft 8

The key insight is that a lonely pixel must be the ONLY black pixel in both its row AND column. Best approach uses two-pass counting: first pass counts blacks per row/column, second pass checks each black pixel. Time: O(mn), Space: O(m+n)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pass with Counting	O(mn)	O(m+n)	First pass counts blacks per row/column, second pass finds lonely pixels
Brute Force - Check Each Position	O(m²n²)	O(1)	For each 'B', scan entire row and column to verify it's alone

Two Pass with Counting — Algorithm Steps

First pass: count black pixels in each row and column
Store counts in arrays
Second pass: for each 'B', check if its row and column counts are both 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Pass

Count blacks in each row and column

Check Pass

For each B, lookup precomputed counts

Result

Count pixels where both row and column have count=1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char picture[][100], int m, int n) {
    // First pass: count blacks in each row and column
    int rowCounts[100] = {0};
    int colCounts[100] = {0};
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (picture[i][j] == 'B') {
                rowCounts[i]++;
                colCounts[j]++;
            }
        }
    }
    
    // Second pass: find lonely pixels
    int lonelyCount = 0;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (picture[i][j] == 'B') {
                if (rowCounts[i] == 1 && colCounts[j] == 1) {
                    lonelyCount++;
                }
            }
        }
    }
    
    return lonelyCount;
}

int main() {
    char picture[100][100];
    int m = 0, n = 0;
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing - assume small input for demo
    char* ptr = line;
    while (*ptr && *ptr != '[') ptr++;
    ptr++; // skip first [
    
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr == '"') {
                    ptr++;
                    picture[m][n++] = *ptr;
                    ptr += 2; // skip char and quote
                }
                if (*ptr == ',') ptr++;
            }
            m++;
            if (*ptr == ']') ptr++;
        }
        if (*ptr == ',') ptr++;
    }
    
    printf("%d\n", solution(picture, m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(mn)

Two passes through m×n matrix, each cell visited exactly twice

✓ Linear Growth

Space Complexity

O(m+n)

Arrays to store row counts (size m) and column counts (size n)

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pass with Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler