# LeetCode 531: Lonely Pixel I

## Problem Restatement

We are given an `m x n` picture.

Each cell is either:

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

A black pixel is lonely if it is the only black pixel in its row and also the only black pixel in its column.

We need to return the number of lonely black pixels.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A 2D character array `picture` |
| Output | The number of lonely black pixels |
| Cell values | `"B"` or `"W"` |
| Lonely condition | Row count is `1` and column count is `1` |

Function shape:

```python
def findLonelyPixel(picture: list[list[str]]) -> int:
    ...
```

## Examples

Consider:

```python
picture = [
    ["W", "W", "B"],
    ["W", "B", "W"],
    ["B", "W", "W"],
]
```

There are three black pixels:

```text
(0, 2)
(1, 1)
(2, 0)
```

Each one is the only black pixel in its row.

Each one is also the only black pixel in its column.

So the answer is:

```python
3
```

Now consider:

```python
picture = [
    ["W", "W", "B"],
    ["W", "B", "W"],
    ["B", "B", "W"],
]
```

The black pixel at `(1, 1)` is not lonely because column `1` also has another black pixel at `(2, 1)`.

The black pixel at `(2, 1)` is not lonely because row `2` has another black pixel at `(2, 0)`.

Only `(0, 2)` is lonely.

So the answer is:

```python
1
```

## First Thought: Check Every Black Pixel Directly

A direct method is to scan the board.

Whenever we find a black pixel, we check its whole row and whole column.

If no other black pixel appears in either direction, we count it.

This works, but it repeats work.

For each black pixel, checking the row costs `O(n)` and checking the column costs `O(m)`. In the worst case, there may be many black pixels, so this becomes inefficient.

## Key Insight

A black pixel is lonely exactly when:

```python
row_count[row] == 1
```

and:

```python
col_count[col] == 1
```

So we should first count how many black pixels appear in every row and every column.

Then each cell can be checked in constant time.

This turns repeated row and column scans into two simple passes over the matrix.

## Algorithm

Create two arrays:

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

First pass:

1. Visit every cell.
2. If the cell is `"B"`, increment its row count.
3. Also increment its column count.

Second pass:

1. Visit every cell again.
2. If the cell is `"B"`, check whether its row count is `1`.
3. Also check whether its column count is `1`.
4. If both are true, increment the answer.

Return the answer.

## Correctness

The first pass counts every black pixel in each row and each column.

Therefore, for any cell `(r, c)`, `row_count[r]` is exactly the number of black pixels in row `r`, and `col_count[c]` is exactly the number of black pixels in column `c`.

A black pixel at `(r, c)` is lonely precisely when there are no other black pixels in row `r` and no other black pixels in column `c`.

Since the pixel itself is black, this condition is equivalent to:

```python
row_count[r] == 1
```

and:

```python
col_count[c] == 1
```

The second pass counts exactly the black pixels satisfying both conditions.

Therefore, the algorithm returns the number of lonely black pixels.

## 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 twice |
| Space | `O(m + n)` | We store one count per row and one count per column |

## Implementation

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

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

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

        answer = 0

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

        return answer
```

## Code Explanation

We first read the matrix dimensions:

```python
m = len(picture)
n = len(picture[0])
```

Then we create arrays for row and column counts:

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

When we see a black pixel:

```python
if picture[r][c] == "B":
```

we update both counts:

```python
row_count[r] += 1
col_count[c] += 1
```

After the first pass, we know the full row and column information.

The second pass checks each black pixel:

```python
if picture[r][c] == "B" and row_count[r] == 1 and col_count[c] == 1:
```

If the row has exactly one black pixel and the column has exactly one black pixel, then this black pixel is lonely.

## Slightly Optimized Second Pass

After counting, we only need to inspect rows with exactly one black pixel.

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

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

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

        answer = 0

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

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

        return answer
```

This has the same asymptotic complexity, but it avoids unnecessary checks in rows that cannot contain a lonely pixel.

## Testing

```python
def run_tests():
    s = Solution()

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

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

    assert s.findLonelyPixel([
        ["W", "W"],
        ["W", "W"],
    ]) == 0

    assert s.findLonelyPixel([
        ["B"],
    ]) == 1

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

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Diagonal black pixels | Every black pixel is lonely |
| Shared row and column | Only one pixel remains lonely |
| No black pixels | Answer should be `0` |
| Single black pixel | Smallest lonely case |
| Same row black pixels | No pixel in that row can be lonely |