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 II

Number: 533

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an m x n picture (2D grid) where each cell is either 'B' (black) or 'W' (white) and an integer target, return the number of black lonely pixels. A black pixel at (r, c) is considered lonely if:

  • Row r and column c each contain exactly target black pixels.
  • For every row that has a black pixel at column c, that row is exactly the same as row r.

Key Insights

  • We must count black pixels per row and per column.
  • Only rows with exactly target black pixels can possibly contribute.
  • For a potential valid row, all black pixels in that row must lie in columns that also have exactly target black pixels.
  • Identical rows that meet the criteria can be grouped together; however, they are only valid if the group size equals target.
  • The final answer is the sum of valid black pixels in these qualifying rows.

Space and Time Complexity

Time Complexity: O(m * n)
Space Complexity: O(m * n) in the worst-case due to storing row strings and column counts.

Solution

We use a two-step approach:

  1. Process each row to:
    • Count black pixels in the row.
    • Build a string representation of the row.
    • Maintain a frequency map for rows that have exactly target black pixels.
    • At the same time, update a column counter to track black pixels per column.
  2. For each row pattern in our frequency map:
    • Check that the frequency equals target (ensuring exactly target rows are identical).
    • For every column position with a black pixel in the row pattern, verify that its column count is exactly target.
    • If valid, every black pixel in these rows is counted toward the result (each valid row contributes target valid pixels).

This approach leverages simple counting with hash maps and arrays and ensures that we only count pixels that satisfy both the row and column conditions.

Code Solutions

class Solution:
    def findLonelyPixel(self, picture: List[List[str]], target: int) -> int:
        if not picture:
            return 0
        
        m, n = len(picture), len(picture[0])
        col_count = [0] * n  # Count of 'B' in each column
        row_pattern_freq = {}  # Map row pattern to frequency
        
        # Process each row to build row patterns and count columns
        for row in picture:
            row_str = ''.join(row)
            # Update frequency only if row's black pixel count equals target
            if row_str.count('B') == target:
                row_pattern_freq[row_str] = row_pattern_freq.get(row_str, 0) + 1
            # Update column counts
            for j, pixel in enumerate(row):
                if pixel == 'B':
                    col_count[j] += 1
        
        result = 0
        # Verify each group of rows sharing the same pattern
        for pattern, frequency in row_pattern_freq.items():
            # The group must have exactly target rows for the column identical check
            if frequency != target:
                continue
            valid = True
            # For each black pixel in the row pattern, check column count
            for j, pixel in enumerate(pattern):
                if pixel == 'B':
                    if col_count[j] != target:
                        valid = False
                        break
            if valid:
                # Each valid row has 'target' black pixels
                result += target * frequency
        return result
← Back to All Questions