LeetCode 531 - Lonely Pixel I

The problem gives us a 2D grid called picture, where each cell contains either: - 'B', representing a black pixel - 'W', representing a white pixel We need to count how many lonely black pixels exist in the matrix. A black pixel is considered lonely if: 1. It is black ('B') 2.

leetcodemediumarrayhash-tablematrix

LeetCode Problem 531

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

Solution

Problem Understanding

The problem gives us a 2D grid called picture, where each cell contains either:

  • 'B', representing a black pixel
  • 'W', representing a white pixel

We need to count how many lonely black pixels exist in the matrix.

A black pixel is considered lonely if:

  1. It is black ('B')
  2. There are no other black pixels in the same row
  3. There are no other black pixels in the same column

In other words, if a cell (row, col) contains 'B', then that row must contain exactly one black pixel, and that column must also contain exactly one black pixel.

For example, consider this matrix:

W W B
W B W
B W W

Each row contains exactly one black pixel, and each column also contains exactly one black pixel. Therefore, all three black pixels are lonely.

Now consider:

B B B
B B W
B B B

Even though there are black pixels, every row and column contains multiple black pixels. Since no black pixel is unique in both its row and column, the answer is 0.

The constraints tell us that:

  • 1 <= m, n <= 500
  • The matrix size can be as large as 500 × 500 = 250,000 cells.

This means a quadratic or cubic solution may become expensive. We should aim for an algorithm that processes the matrix efficiently, ideally in linear time relative to the number of cells.

There are several edge cases worth considering:

  • A matrix with only one cell, [['B']], should return 1 because the single black pixel is automatically lonely.
  • A matrix with only white pixels should return 0.
  • A row may contain exactly one black pixel, but its column may contain multiple black pixels, which means it is not lonely.
  • Likewise, a column may contain exactly one black pixel while its row contains several black pixels.

The problem guarantees that the matrix dimensions are valid and every entry is either 'B' or 'W', so we do not need additional input validation.

Approaches

Brute Force Approach

A straightforward idea is to inspect every black pixel individually and check whether it is lonely.

For every cell containing 'B', we can scan its entire row to count black pixels and then scan its entire column to count black pixels. If both counts equal 1, then the pixel is lonely.

This approach is correct because it directly follows the problem definition. Every candidate black pixel is verified against the exact loneliness conditions.

However, it is inefficient. Suppose the matrix has m rows and n columns. For each cell, we may scan an entire row and an entire column. Since there are m × n cells, the total runtime becomes:

O(m × n × (m + n))

With dimensions up to 500 × 500, this repeated rescanning becomes unnecessarily expensive.

Optimal Approach

The key observation is that we repeatedly recompute the same row and column information.

Instead of checking row and column counts for every black pixel separately, we can preprocess:

  • How many black pixels exist in each row
  • How many black pixels exist in each column

Once we have these counts, determining whether a black pixel is lonely becomes very fast.

The process works in two passes:

  1. Traverse the matrix and count black pixels per row and column.
  2. Traverse again and count black pixels where:
  • row count = 1
  • column count = 1

This avoids repeated scanning and gives us an efficient linear solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(m × n × (m + n)) O(1) For every black pixel, rescans its row and column
Optimal O(m × n) O(m + n) Precompute row and column black counts

Algorithm Walkthrough

Optimal Algorithm

  1. Create two arrays:
  • row_black_count of size m
  • col_black_count of size n

These arrays will store how many black pixels appear in each row and column. Using arrays is efficient because rows and columns are indexed numerically. 2. Traverse the entire matrix once.

For every cell (row, col):

  • If picture[row][col] == 'B'

  • Increment row_black_count[row]

  • Increment col_black_count[col]

After this pass, we know exactly how many black pixels each row and column contains. 3. Traverse the matrix a second time.

For every cell (row, col):

  • If the cell contains 'B'

  • Check whether:

  • row_black_count[row] == 1

  • col_black_count[col] == 1

If both are true, increment the lonely pixel counter. 4. Return the final count.

Why it works

The algorithm works because a black pixel is lonely if and only if its row contains exactly one black pixel and its column contains exactly one black pixel.

The first traversal computes these counts accurately for every row and column. The second traversal simply verifies the loneliness condition for each black pixel. Since every black pixel is checked exactly once against the correct row and column totals, the algorithm always returns the correct number of lonely pixels.

Python Solution

from typing import List

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

        row_black_count = [0] * rows
        col_black_count = [0] * cols

        # First pass: count black pixels in rows and columns
        for row in range(rows):
            for col in range(cols):
                if picture[row][col] == 'B':
                    row_black_count[row] += 1
                    col_black_count[col] += 1

        lonely_pixels = 0

        # Second pass: count lonely black pixels
        for row in range(rows):
            for col in range(cols):
                if (
                    picture[row][col] == 'B'
                    and row_black_count[row] == 1
                    and col_black_count[col] == 1
                ):
                    lonely_pixels += 1

        return lonely_pixels

The implementation follows the exact two-pass strategy described earlier.

The first section initializes two counting arrays. row_black_count stores the number of black pixels in each row, while col_black_count stores the number of black pixels in each column.

The first nested loop traverses the matrix once. Whenever a black pixel is encountered, both counters are updated. This preprocessing step ensures we never need to rescan rows or columns later.

The second nested loop checks every black pixel again. Since row and column counts are already known, determining whether a pixel is lonely becomes a constant-time operation. If both counts equal 1, we increment the answer.

Finally, the method returns the total lonely pixel count.

Go Solution

func findLonelyPixel(picture [][]byte) int {
	rows := len(picture)
	cols := len(picture[0])

	rowBlackCount := make([]int, rows)
	colBlackCount := make([]int, cols)

	// First pass: count black pixels in rows and columns
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if picture[row][col] == 'B' {
				rowBlackCount[row]++
				colBlackCount[col]++
			}
		}
	}

	lonelyPixels := 0

	// Second pass: count lonely black pixels
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if picture[row][col] == 'B' &&
				rowBlackCount[row] == 1 &&
				colBlackCount[col] == 1 {
				lonelyPixels++
			}
		}
	}

	return lonelyPixels
}

The Go implementation mirrors the Python solution closely.

The input uses [][]byte instead of strings, so comparisons are made against the byte literal 'B'. Slices are created using make() for row and column counts.

There is no special handling required for nil or empty matrices because the problem guarantees valid dimensions with at least one row and one column. Integer overflow is not a concern because the maximum count is at most 500, which easily fits within Go's int.

Worked Examples

Example 1

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

First Pass: Count Black Pixels

Position Value Row Counts Column Counts
(0,0) W [0,0,0] [0,0,0]
(0,1) W [0,0,0] [0,0,0]
(0,2) B [1,0,0] [0,0,1]
(1,0) W [1,0,0] [0,0,1]
(1,1) B [1,1,0] [0,1,1]
(1,2) W [1,1,0] [0,1,1]
(2,0) B [1,1,1] [1,1,1]
(2,1) W [1,1,1] [1,1,1]
(2,2) W [1,1,1] [1,1,1]

After preprocessing:

row_black_count = [1,1,1]
col_black_count = [1,1,1]

Second Pass

Position Value Row Count Column Count Lonely?
(0,2) B 1 1 Yes
(1,1) B 1 1 Yes
(2,0) B 1 1 Yes

Final answer:

3

Example 2

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

First Pass

After traversing the matrix:

row_black_count = [3,2,3]
col_black_count = [3,3,2]

Second Pass

Every black pixel fails at least one condition because rows and columns contain multiple black pixels.

Position Row Count Column Count Lonely?
(0,0) 3 3 No
(0,1) 3 3 No
(0,2) 3 2 No
(1,0) 2 3 No
(1,1) 2 3 No
(2,0) 3 3 No
(2,1) 3 3 No
(2,2) 3 2 No

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(m × n) We traverse the matrix twice, each traversal touches every cell once
Space O(m + n) Two counting arrays store row and column black pixel frequencies

The runtime is linear with respect to the number of cells in the matrix. Even though we perform two passes, constants are ignored in Big O notation, so the complexity remains O(m × n).

The extra memory comes from storing row and column counts. Since we maintain one array of length m and another of length n, the total auxiliary space is O(m + n).

Test Cases

from typing import List

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

        row_black_count = [0] * rows
        col_black_count = [0] * cols

        for row in range(rows):
            for col in range(cols):
                if picture[row][col] == 'B':
                    row_black_count[row] += 1
                    col_black_count[col] += 1

        lonely_pixels = 0

        for row in range(rows):
            for col in range(cols):
                if (
                    picture[row][col] == 'B'
                    and row_black_count[row] == 1
                    and col_black_count[col] == 1
                ):
                    lonely_pixels += 1

        return lonely_pixels

solution = Solution()

assert solution.findLonelyPixel(
    [["W","W","B"],["W","B","W"],["B","W","W"]]
) == 3  # Example 1

assert solution.findLonelyPixel(
    [["B","B","B"],["B","B","W"],["B","B","B"]]
) == 0  # Example 2

assert solution.findLonelyPixel(
    [["B"]]
) == 1  # Single black pixel

assert solution.findLonelyPixel(
    [["W"]]
) == 0  # Single white pixel

assert solution.findLonelyPixel(
    [["B","W"],["W","W"]]
) == 1  # One lonely pixel

assert solution.findLonelyPixel(
    [["B","B"],["W","W"]]
) == 0  # Row has multiple black pixels

assert solution.findLonelyPixel(
    [["B","W"],["B","W"]]
) == 0  # Column has multiple black pixels

assert solution.findLonelyPixel(
    [["W","W"],["W","W"]]
) == 0  # No black pixels

assert solution.findLonelyPixel(
    [["W","B","W"],["W","W","W"],["W","W","B"]]
) == 2  # Multiple lonely pixels

assert solution.findLonelyPixel(
    [["B","W","W","W","B"]]
) == 0  # Single row with multiple black pixels
Test Why
[[W,W,B],[W,B,W],[B,W,W]] Validates the first example with multiple lonely pixels
[[B,B,B],[B,B,W],[B,B,B]] Validates the second example where no pixel qualifies
[[B]] Smallest valid input with a lonely black pixel
[[W]] Smallest valid input with no black pixels
[[B,W],[W,W]] Confirms one valid lonely pixel
[[B,B],[W,W]] Tests row conflict
[[B,W],[B,W]] Tests column conflict
[[W,W],[W,W]] Ensures all-white matrix returns zero
Sparse diagonal black pixels Verifies multiple isolated lonely pixels
Single-row matrix Ensures row uniqueness rule is enforced

Edge Cases

Single Cell Matrix

A matrix like [['B']] is an important edge case because both the row and column contain exactly one black pixel by definition. A careless implementation might incorrectly assume at least two rows or columns exist. Our solution handles this naturally because both count arrays correctly record a value of 1.

Multiple Black Pixels in the Same Row

Consider:

B B
W W

Although the black pixels occupy unique columns, neither pixel is lonely because the row contains more than one black pixel. A buggy implementation might only check column uniqueness. Our solution prevents this by requiring row_black_count[row] == 1.

Multiple Black Pixels in the Same Column

Consider:

B W
B W

Here, both rows contain only one black pixel, but the column contains two black pixels. Neither pixel is lonely. This case demonstrates why both row and column uniqueness are necessary. The implementation explicitly verifies both conditions before counting a pixel.

Matrix With No Black Pixels

A matrix containing only 'W' pixels should return 0. Since no black pixels are encountered during traversal, both count arrays remain all zeros, and the second pass never increments the answer. The algorithm handles this efficiently without any special-case logic.