We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lonely Pixel I

Number: 531

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

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 defined as a 'B' that is the only 'B' in both its row and its column.

Key Insights

  • Count the number of 'B' pixels in each row.
  • Count the number of 'B' pixels in each column.
  • A pixel is considered lonely if the count in its corresponding row and column is exactly 1.
  • Two passes through the matrix can efficiently solve the problem: one for counting and one for checking conditions.

Space and Time Complexity

Time Complexity: O(m * n), where m and n are the dimensions of the picture. Space Complexity: O(m + n), used to store the row and column counts.

Solution

The solution works by first scanning the entire matrix to compute the number of black pixels in each row and each column using two arrays/lists. Once these counts are available, a second pass through the matrix determines for each black pixel if it is lonely by checking if its corresponding row and column count equals 1. The approach uses simple array data structures for tallying counts and ensures that each element is processed only a constant number of times.

Code Solutions

# Function to find the number of lonely black pixels in a picture.
def findLonelyPixel(picture):
    # Get dimensions of the picture
    rows = len(picture)
    cols = len(picture[0]) if rows > 0 else 0

    # Initialize row and column counts with zeros
    rowCount = [0] * rows
    colCount = [0] * cols

    # First pass: Count the number of 'B's in each row and column.
    for i in range(rows):
        for j in range(cols):
            if picture[i][j] == 'B':
                rowCount[i] += 1
                colCount[j] += 1

    # Second pass: Check for lonely black pixels.
    lonelyPixels = 0
    for i in range(rows):
        for j in range(cols):
            if picture[i][j] == 'B' and rowCount[i] == 1 and colCount[j] == 1:
                lonelyPixels += 1

    return lonelyPixels

# Example test
picture = [["W","W","B"], ["W","B","W"], ["B","W","W"]]
print(findLonelyPixel(picture))  # Output: 3
← Back to All Questions