LeetCode 533 - Lonely Pixel II

The problem gives us a matrix called picture, where each cell contains either 'B' for a black pixel or 'W' for a white pixel. We are also given an integer target. We need to count how many black pixels qualify as "lonely pixels" under two strict conditions.

leetcodemediumarrayhash-tablematrix

LeetCode Problem 533

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Matrix

Solution

Problem Understanding

The problem gives us a matrix called picture, where each cell contains either 'B' for a black pixel or 'W' for a white pixel. We are also given an integer target.

We need to count how many black pixels qualify as "lonely pixels" under two strict conditions.

Suppose a black pixel is located at position (r, c).

First, row r must contain exactly target black pixels, and column c must also contain exactly target black pixels.

Second, every row that has a black pixel in column c must be identical to row r. This is the more subtle requirement. It means that if column c contains black pixels in several rows, all of those rows must have exactly the same pattern of black and white pixels.

The output is the total number of black pixels satisfying both conditions.

The constraints are important:

  • m and n are each at most 200
  • The matrix contains only 'B' and 'W'
  • target is at most min(m, n)

A 200 x 200 matrix contains at most 40,000 cells, which is small enough for solutions around O(m * n) or O(m * n * k) for small extra factors. However, extremely expensive brute force checks across many rows and columns repeatedly could become inefficient.

There are several important edge cases:

  • A row may contain fewer or more than target black pixels, immediately disqualifying all pixels in that row.
  • A column may contain exactly target black pixels, but the corresponding rows may not be identical.
  • Multiple identical rows may appear many times, and only some columns may satisfy the column-count condition.
  • A matrix with all white pixels should return 0.
  • A matrix with all black pixels usually fails because row and column counts become too large relative to target.

The key challenge is efficiently verifying the second condition without repeatedly comparing entire rows for every black pixel.

Approaches

Brute Force Approach

A straightforward solution is to inspect every black pixel individually.

For each black pixel (r, c):

  1. Count how many black pixels exist in row r.
  2. Count how many black pixels exist in column c.
  3. If both equal target, examine every row that contains a black pixel in column c.
  4. Compare each of those rows against row r to ensure they are identical.

This approach is correct because it directly checks the problem definition for every candidate black pixel.

However, it is inefficient because row comparisons are repeatedly performed for many pixels. In the worst case, every validation may require scanning large parts of the matrix multiple times.

Optimal Approach

The key observation is that rows matter more than individual pixels.

If a row is valid, then:

  • It must contain exactly target black pixels.
  • Any column contributing to the answer must contain exactly target black pixels.
  • Every row containing a black pixel in that column must be identical.

Instead of repeatedly comparing rows, we can group identical rows together using a hash map.

The idea is:

  1. Count black pixels in every column.
  2. Convert each row into a string representation.
  3. Count how many times each unique row pattern appears.
  4. Only consider row patterns that:
  • contain exactly target black pixels
  • appear exactly target times

Why does "appear exactly target times" matter?

Suppose a row pattern has black pixels in certain columns. If the row appears exactly target times, and a column containing a black pixel also has exactly target black pixels total, then all black pixels in that column must come from those identical rows. This automatically satisfies the second condition.

This transforms expensive repeated row comparisons into efficient hash map lookups.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * (m + n)) O(1) Repeatedly validates rows and columns for each black pixel
Optimal O(m * n) O(m * n) Uses row hashing and column counts to avoid repeated comparisons

Algorithm Walkthrough

  1. Compute the number of black pixels in each column.

Create an array column_black_count of size n.

Traverse the matrix once. Whenever we see a 'B' at (r, c), increment column_black_count[c].

We do this because every valid lonely pixel must belong to a column containing exactly target black pixels. 2. Convert each row into a hashable representation.

Since lists cannot be dictionary keys directly, convert each row into a string such as "WBWBBW".

Store the frequency of each row pattern in a hash map called row_frequency.

This lets us quickly determine how many times an identical row appears. 3. Process only candidate rows.

Iterate through every row again.

For each row:

  • Count the number of black pixels.
  • Skip the row if the count is not exactly target.

This immediately removes rows that cannot contribute to the answer. 4. Check whether the row pattern appears exactly target times.

Let row_string be the string representation of the row.

If row_frequency[row_string] != target, skip this row.

Why?

If a row pattern appears more or fewer than target times, then the required column structure cannot match the problem constraints. 5. Validate each black column.

For every column c where the row contains 'B':

  • Check whether column_black_count[c] == target.

If true, then every black pixel in that column comes from the identical rows represented by row_string.

Therefore, all black pixels in that column satisfy both conditions. 6. Accumulate the answer.

Every valid column contributes one lonely pixel for the current row.

Add the number of valid columns to the result.

Why it works

The algorithm relies on an important invariant:

If a row pattern appears exactly target times, and a column containing 'B' also contains exactly target black pixels, then every black pixel in that column must belong to those identical rows.

This automatically guarantees:

  • the row contains exactly target black pixels
  • the column contains exactly target black pixels
  • every row contributing to the column is identical

Therefore, every counted pixel satisfies the definition of a black lonely pixel.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def findBlackPixel(self, picture: List[List[str]], target: int) -> int:
        rows = len(picture)
        cols = len(picture[0])

        # Count black pixels in each column
        column_black_count = [0] * cols

        # Store row string frequencies
        row_frequency = Counter()

        for row in picture:
            row_string = ''.join(row)
            row_frequency[row_string] += 1

            for c in range(cols):
                if row[c] == 'B':
                    column_black_count[c] += 1

        result = 0

        # Process candidate rows
        for row in picture:
            row_string = ''.join(row)

            # Row must appear exactly target times
            if row_frequency[row_string] != target:
                continue

            # Row must contain exactly target black pixels
            if row_string.count('B') != target:
                continue

            # Check valid columns
            for c in range(cols):
                if row[c] == 'B' and column_black_count[c] == target:
                    result += 1

        return result

The implementation closely follows the algorithm described earlier.

The first loop performs two tasks simultaneously. It builds the frequency map of row patterns and computes the number of black pixels in each column. Combining these operations keeps the implementation efficient and avoids unnecessary passes over the matrix.

The Counter data structure is ideal because it allows constant time lookup of how many times a row pattern appears.

In the second phase, each row is examined as a candidate row. Rows that do not contain exactly target black pixels are skipped immediately. Rows whose pattern frequency is not exactly target are also skipped.

Finally, the algorithm scans each black pixel in the row and checks whether its column contains exactly target black pixels. Every such position contributes to the final answer.

Because the problem guarantees that all identical rows are grouped logically through the frequency map, no explicit row comparisons are necessary during validation.

Go Solution

func findBlackPixel(picture [][]byte, target int) int {
	rows := len(picture)
	cols := len(picture[0])

	columnBlackCount := make([]int, cols)
	rowFrequency := make(map[string]int)

	// Build column counts and row frequencies
	for _, row := range picture {
		rowString := string(row)
		rowFrequency[rowString]++

		for c := 0; c < cols; c++ {
			if row[c] == 'B' {
				columnBlackCount[c]++
			}
		}
	}

	result := 0

	// Process candidate rows
	for _, row := range picture {
		rowString := string(row)

		if rowFrequency[rowString] != target {
			continue
		}

		blackCount := 0
		for c := 0; c < cols; c++ {
			if row[c] == 'B' {
				blackCount++
			}
		}

		if blackCount != target {
			continue
		}

		for c := 0; c < cols; c++ {
			if row[c] == 'B' && columnBlackCount[c] == target {
				result++
			}
		}
	}

	return result
}

The Go implementation follows the same logic as the Python solution.

One notable difference is that Go uses map[string]int instead of Python's Counter. Rows are converted from []byte into strings so they can be used as map keys.

Go does not provide a built in string counting method like Python's count, so the implementation explicitly counts black pixels using a loop.

There are no integer overflow concerns because the matrix size is at most 200 x 200, meaning the result cannot exceed 40,000.

Worked Examples

Example 1

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

Step 1: Compute column black counts

Column Black Count
0 0
1 3
2 1
3 3
4 4
5 0

Step 2: Build row frequencies

Row String Frequency
WBWBBW 3
WWBWBW 1

Step 3: Process rows

Consider row:

WBWBBW
  • Frequency = 3
  • Black count = 3
  • Valid candidate row

Now inspect black columns:

Column Value Column Count Valid?
1 B 3 Yes
3 B 3 Yes
4 B 4 No

Each valid row contributes 2 lonely pixels.

Since this row appears 3 times:

2 * 3 = 6

Final answer:

6

Example 2

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

target = 1

Step 1: Compute column counts

Column Black Count
0 0
1 0
2 3

Step 2: Build row frequencies

Row String Frequency
WWB 3

Step 3: Validate rows

The row WWB:

  • appears 3 times
  • target is 1

Since frequency does not equal target, the row is rejected immediately.

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is processed a constant number of times
Space O(m * n) Hash map stores up to m row strings of length n

The algorithm performs a few full traversals of the matrix, but each traversal is linear in the number of cells. No nested repeated row comparisons occur.

The extra space comes primarily from storing row patterns in the frequency map. In the worst case, all rows are unique, requiring storage proportional to the size of the matrix.

Test Cases

from typing import List

class Solution:
    def findBlackPixel(self, picture: List[List[str]], target: int) -> int:
        from collections import Counter

        rows = len(picture)
        cols = len(picture[0])

        column_black_count = [0] * cols
        row_frequency = Counter()

        for row in picture:
            row_string = ''.join(row)
            row_frequency[row_string] += 1

            for c in range(cols):
                if row[c] == 'B':
                    column_black_count[c] += 1

        result = 0

        for row in picture:
            row_string = ''.join(row)

            if row_frequency[row_string] != target:
                continue

            if row_string.count('B') != target:
                continue

            for c in range(cols):
                if row[c] == 'B' and column_black_count[c] == target:
                    result += 1

        return result

solution = Solution()

# Example 1
assert solution.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  # Standard example with valid lonely pixels

# Example 2
assert solution.findBlackPixel(
    [
        ["W","W","B"],
        ["W","W","B"],
        ["W","W","B"]
    ],
    1
) == 0  # Column count exceeds target

# Single cell black
assert solution.findBlackPixel(
    [["B"]],
    1
) == 1  # Smallest valid case

# Single cell white
assert solution.findBlackPixel(
    [["W"]],
    1
) == 0  # No black pixels

# All rows identical and valid
assert solution.findBlackPixel(
    [
        ["B","W"],
        ["B","W"]
    ],
    2
) == 2  # Both black pixels are valid

# Row count valid but column count invalid
assert solution.findBlackPixel(
    [
        ["B","W"],
        ["B","W"],
        ["B","W"]
    ],
    2
) == 0  # Column has too many black pixels

# Mixed patterns
assert solution.findBlackPixel(
    [
        ["B","W","B"],
        ["B","W","B"],
        ["W","B","W"]
    ],
    2
) == 4  # Two identical valid rows

# No identical rows
assert solution.findBlackPixel(
    [
        ["B","W"],
        ["W","B"]
    ],
    1
) == 2  # Each black pixel independently valid
Test Why
Example 1 Validates the main intended scenario
Example 2 Ensures invalid column counts are rejected
Single black cell Tests smallest valid input
Single white cell Tests empty answer case
Identical valid rows Confirms repeated row handling
Invalid column count Ensures column validation works
Mixed patterns Tests partial validity among rows
No identical rows Verifies isolated valid pixels

Edge Cases

One important edge case occurs when multiple rows are identical, but the corresponding columns contain more than target black pixels. A naive implementation might incorrectly count these pixels simply because the rows match. The algorithm avoids this by explicitly checking column_black_count[c] == target before counting a pixel.

Another tricky case happens when a row contains exactly target black pixels, but the row pattern appears more or fewer than target times. Even if the column counts seem correct individually, the second rule fails because not all contributing rows are identical in the required way. The frequency map check ensures these rows are rejected immediately.

A third edge case involves very small matrices, such as 1 x 1. These cases are easy to mishandle because the single cell simultaneously belongs to the only row and only column. The implementation naturally handles this because the row count, column count, and frequency checks all still apply correctly.

Another subtle situation is when all pixels are black. For example:

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

with target = 1.

Every row and column contains too many black pixels, so the answer should be 0. The algorithm correctly rejects every candidate because both row and column counts exceed the target value.