Code Implementation

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        if not picture or not picture[0]:
            return 0
        rows = len(picture)
        cols = len(picture[0])
        row_count = [0] * rows
        col_count = [0] * cols

        # Count 'B's in each row and column
        for i in range(rows):
            for j in range(cols):
                if picture[i][j] == 'B':
                    row_count[i] += 1
                    col_count[j] += 1

        # Find lonely pixels
        lonely = 0
        for i in range(rows):
            for j in range(cols):
                if picture[i][j] == 'B' and row_count[i] == 1 and col_count[j] == 1:
                    lonely += 1
        return lonely
      

class Solution {
public:
    int findLonelyPixel(vector<vector<char>>& picture) {
        int rows = picture.size();
        if (rows == 0) return 0;
        int cols = picture[0].size();
        vector<int> row_count(rows, 0);
        vector<int> col_count(cols, 0);

        // Count 'B's in each row and column
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (picture[i][j] == 'B') {
                    row_count[i]++;
                    col_count[j]++;
                }
            }
        }

        // Find lonely pixels
        int lonely = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (picture[i][j] == 'B' && row_count[i] == 1 && col_count[j] == 1) {
                    lonely++;
                }
            }
        }
        return lonely;
    }
};
      

class Solution {
    public int findLonelyPixel(char[][] picture) {
        int rows = picture.length;
        if (rows == 0) return 0;
        int cols = picture[0].length;
        int[] rowCount = new int[rows];
        int[] colCount = new int[cols];

        // Count 'B's in each row and column
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (picture[i][j] == 'B') {
                    rowCount[i]++;
                    colCount[j]++;
                }
            }
        }

        // Find lonely pixels
        int lonely = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (picture[i][j] == 'B' && rowCount[i] == 1 && colCount[j] == 1) {
                    lonely++;
                }
            }
        }
        return lonely;
    }
}
      

var findLonelyPixel = function(picture) {
    if (!picture || picture.length === 0) return 0;
    let rows = picture.length;
    let cols = picture[0].length;
    let rowCount = new Array(rows).fill(0);
    let colCount = new Array(cols).fill(0);

    // Count 'B's in each row and column
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (picture[i][j] === 'B') {
                rowCount[i]++;
                colCount[j]++;
            }
        }
    }

    // Find lonely pixels
    let lonely = 0;
    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (picture[i][j] === 'B' && rowCount[i] === 1 && colCount[j] === 1) {
                lonely++;
            }
        }
    }
    return lonely;
};
      

Problem Description

The "Lonely Pixel I" problem asks you to find the number of black lonely pixels in a given picture. The picture is represented as a 2D array called picture, where each element is either 'B' (for black) or 'W' (for white). A lonely pixel is defined as a pixel that is black ('B') and is the only black pixel in both its row and its column.

Key constraints:

• Each black pixel can only be counted if it is the only 'B' in both its row and its column.
• Do not count pixels that share their row or column with any other 'B'.
• The input is a 2D array of characters.

Thought Process

At first glance, you might think about checking every pixel in the grid and, for each black pixel, scanning its entire row and column to see if it is the only 'B'. While this works, it is inefficient, especially for larger grids, because it repeats work for each pixel.

To optimize, we can precompute how many black pixels are in each row and each column. If we know these counts, we can simply check, for any pixel, whether its row and column each have exactly one black pixel. This way, we avoid repeatedly scanning rows and columns.

This approach is similar to "marking" all the rows and columns in a single pass and then using this information to quickly decide for any pixel whether it is lonely.

Solution Approach

• Step 1: Create two arrays: one to store the count of black pixels in each row, and another for each column.
• Step 2: Traverse the entire picture grid. For every 'B' found at position (i, j), increment the count at row_count[i] and col_count[j].
• Step 3: After counting, iterate through the grid again. For every 'B' at (i, j), check if row_count[i] and col_count[j] are both exactly 1.
• Step 4: If both counts are 1, increment your answer counter, since this pixel is lonely.
• Step 5: Return the total count of lonely pixels.

We use arrays for row and column counts because accessing an array by index is very fast (constant time), which makes our final solution efficient.

Example Walkthrough

Let's use the following sample input:

picture = [
  ['W', 'B', 'W'],
  ['W', 'B', 'W'],
  ['W', 'W', 'B']
]
  

• Step 1: Count black pixels in each row and column:
  • Row counts: [1, 1, 1]
  • Column counts: [0, 2, 1]
• Step 2: Check each 'B':
  • At (0,1): row_count[0]=1, col_count[1]=2 → Not lonely
  • At (1,1): row_count[1]=1, col_count[1]=2 → Not lonely
  • At (2,2): row_count[2]=1, col_count[2]=1 → Lonely!
• Step 3: Only one lonely pixel found at (2,2).

Time and Space Complexity

• Brute-force approach: For each 'B', scan its row and column (O(m+n) per pixel), so total O(m * n * (m + n)), where m and n are the number of rows and columns.
• Optimized approach:
  • First pass to count rows and columns: O(m * n)
  • Second pass to check each pixel: O(m * n)
  • Total time: O(m * n)
  • Space: O(m + n) for row and column count arrays

The optimized approach is much faster and uses only a small amount of extra memory.

Summary

The key to solving the "Lonely Pixel I" problem efficiently is to use precomputed counts for each row and column. This allows us to quickly check, for any black pixel, if it is the only one in its row and column, without rescanning the grid multiple times. The approach is elegant, simple, and scales well for large inputs.