# LeetCode 533: Lonely Pixel II

## Problem Restatement

We are given an `m x n` picture.

Each cell is either:

| Character | Meaning |
|---|---|
| `"B"` | Black pixel |
| `"W"` | White pixel |

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

| Item | Meaning |
|---|---|
| Input | A 2D character array `picture` and an integer `target` |
| Output | The number of valid black lonely pixels |
| Cell values | `"B"` or `"W"` |
| Row rule | The row has exactly `target` black pixels |
| Column rule | The column has exactly `target` black pixels |
| Equality rule | All rows with `"B"` in that column are identical |

Function shape:

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

## Examples

Consider:

```python
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:

```python
["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:

```python
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:

```python
row_count[r] == target
```

```python
col_count[c] == target
```

```python
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:

```python
row_count[r] == target
```

```python
col_count[c] == target
```

```python
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.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n)` | We scan the matrix and row strings |
| Space | `O(m * n)` | Row strings may store all row patterns |

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

## Implementation

```python
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:

```python
row_count = [0] * m
```

and each column:

```python
col_count = [0] * n
```

For each row, we also build a string representation:

```python
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:

```python
row_frequency = Counter(row_strings)
```

The second pass skips rows that cannot contribute valid pixels:

```python
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:

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

Then we check black cells in that row:

```python
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

```python
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()
```

| Test | Why |
|---|---|
| Official-style sample | Checks repeated identical rows and rejected mixed column |
| One column with three black pixels | Row count does not match target |
| Diagonal black pixels | Simple `target = 1` case |
| All black `2 x 2` | Every pixel satisfies both rules |
| Repeated row pattern | Checks row-frequency condition |