LeetCode 533: Lonely Pixel II

Problem Restatement

We are given an m x n picture.

Each cell is either:

We are also given an integer target.

We need to count black pixels located at some position (r, c) such that both rules are true:

1. Row r contains exactly target black pixels, and column c also contains exactly target black pixels.
2. Every row that has a black pixel in column c must be exactly the same as row r.

So this problem is stricter than Lonely Pixel I. A pixel is not enough by itself. Its whole row pattern matters too. The official condition says rows with a black pixel in the same column must be identical to the candidate row.

Input and Output

Function shape:

def findBlackPixel(picture: list[list[str]], target: int) -> int:
    ...

Examples

Consider:

picture = [
    ["W", "B", "W", "B", "B", "W"],
    ["W", "B", "W", "B", "B", "W"],
    ["W", "B", "W", "B", "B", "W"],
    ["W", "W", "B", "W", "B", "W"],
]
target = 3

Rows 0, 1, and 2 are identical:

["W", "B", "W", "B", "B", "W"]

Each of those rows has exactly 3 black pixels.

Column 1 has black pixels in rows 0, 1, and 2, so it has exactly 3 black pixels. These rows are all identical.

Therefore, the three black pixels in column 1 are valid.

Column 3 also has black pixels in rows 0, 1, and 2, so it contributes another 3 valid pixels.

The answer is:

6

Column 4 also has black pixels, but it includes row 3, whose row pattern is different. So pixels in column 4 do not all satisfy the row-equality rule.

First Thought: Check Every Black Pixel

A direct solution is to inspect every black pixel (r, c).

For each black pixel:

1. Count black pixels in row r.
2. Count black pixels in column c.
3. Look at every row that has "B" in column c.
4. Check whether all those rows equal row r.

This works, but it repeats the same row and column counting many times.

The matrix can have up to hundreds of rows and columns, so repeated full scans are unnecessary.

Key Insight

For a black pixel (r, c) to be valid, four facts must hold:

row_count[r] == target

col_count[c] == target

picture[r][c] == "B"

and the row pattern of r must appear exactly target times.

Why does row-pattern frequency help?

Suppose row r has "B" at column c, column c has exactly target black pixels, and row r’s pattern appears exactly target times.

If the row pattern has "B" at column c, then every identical copy of this row also has "B" at column c.

There are exactly target copies of the row pattern, and column c has exactly target black pixels. Therefore, the rows with black pixels in column c must be exactly those identical rows.

That satisfies the second rule.

So we can solve the problem by counting:

1. Number of black pixels in each row.
2. Number of black pixels in each column.
3. Frequency of each full row pattern.

Algorithm

First pass over the picture:

1. Convert each row into a string.
2. Count black pixels in each row.
3. Count black pixels in each column.
4. Count how many times each row string appears.

Second pass over the picture:

For every black pixel (r, c), count it if:

row_count[r] == target

col_count[c] == target

row_frequency[row_string[r]] == target

Return the total count.

Correctness

The first pass computes exact row black counts, column black counts, and row-pattern frequencies.

Consider any pixel counted by the algorithm at position (r, c). Since the algorithm only counts cells where picture[r][c] == "B", the cell is black. Since row_count[r] == target and col_count[c] == target, the first rule is satisfied.

It remains to show the second rule. The row pattern of row r appears exactly target times. Since row r has "B" at column c, every identical row also has "B" at column c. Thus these target identical rows all contribute black pixels to column c. Since column c has exactly target black pixels total, there cannot be any additional different row with a black pixel in column c. Therefore, every row with a black pixel in column c is identical to row r.

So every counted pixel is valid.

Now consider any valid black pixel (r, c). By rule 1, its row and column both contain exactly target black pixels. By rule 2, all rows with black pixels in column c are identical to row r. Since column c has exactly target black pixels, there are exactly target such rows. Therefore, row r’s pattern appears at least target times.

It cannot appear more than target times. If an extra identical row existed, it would also have "B" at column c, which would make column c contain more than target black pixels. So the row pattern appears exactly target times.

Thus the algorithm counts every valid pixel.

Complexity

Let m be the number of rows and n be the number of columns.

The count arrays use O(m + n) space. The row-pattern map dominates in the worst case.

Implementation

from collections import Counter

class Solution:
    def findBlackPixel(self, picture: list[list[str]], target: int) -> int:
        m = len(picture)
        n = len(picture[0])

        row_count = [0] * m
        col_count = [0] * n
        row_strings = []

        for r in range(m):
            row_black = 0

            for c in range(n):
                if picture[r][c] == "B":
                    row_black += 1
                    col_count[c] += 1

            row_count[r] = row_black
            row_strings.append("".join(picture[r]))

        row_frequency = Counter(row_strings)

        answer = 0

        for r in range(m):
            if row_count[r] != target:
                continue

            if row_frequency[row_strings[r]] != target:
                continue

            for c in range(n):
                if picture[r][c] == "B" and col_count[c] == target:
                    answer += 1

        return answer

Code Explanation

We store the number of black pixels in each row:

row_count = [0] * m

and each column:

col_count = [0] * n

For each row, we also build a string representation:

row_strings.append("".join(picture[r]))

This lets us compare whole row patterns cheaply through hashing.

Then we count how often each row pattern appears:

row_frequency = Counter(row_strings)

The second pass skips rows that cannot contribute valid pixels:

if row_count[r] != target:
    continue

A valid pixel must come from a row with exactly target black pixels.

We also skip rows whose full pattern does not occur exactly target times:

if row_frequency[row_strings[r]] != target:
    continue

Then we check black cells in that row:

if picture[r][c] == "B" and col_count[c] == target:
    answer += 1

At this point, the row rule, column rule, and row-equality rule are all satisfied.

Testing

def run_tests():
    s = Solution()

    assert s.findBlackPixel([
        ["W", "B", "W", "B", "B", "W"],
        ["W", "B", "W", "B", "B", "W"],
        ["W", "B", "W", "B", "B", "W"],
        ["W", "W", "B", "W", "B", "W"],
    ], 3) == 6

    assert s.findBlackPixel([
        ["W", "B", "W"],
        ["W", "B", "W"],
        ["W", "B", "W"],
    ], 3) == 0

    assert s.findBlackPixel([
        ["B", "W"],
        ["W", "B"],
    ], 1) == 2

    assert s.findBlackPixel([
        ["B", "B"],
        ["B", "B"],
    ], 2) == 4

    assert s.findBlackPixel([
        ["B", "W", "B"],
        ["B", "W", "B"],
        ["W", "B", "W"],
    ], 2) == 4

    print("all tests passed")

run_tests()