LeetCode 531: Lonely Pixel I

Problem Restatement

We are given an m x n picture.

Each cell is either:

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

Function shape:

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

Examples

Consider:

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

There are three black pixels:

(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:

3

Now consider:

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:

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:

row_count[row] == 1

and:

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:

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:

row_count[r] == 1

and:

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.

Implementation

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:

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

Then we create arrays for row and column counts:

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

When we see a black pixel:

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

we update both counts:

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:

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.

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

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