⚡Flashcard Drill➔
NeetCode #23LC-531MediumArrays & HashingNC Algo100
← Back to All Problems

#23 · #531 · Lonely Pixel I(孤独像素 I)

📌 Problem Statement & Constraints

Given an m x n picture consisting of black 'B' and white 'W' pixels, return the number of lonely black pixels. A black pixel at (i, j) is lonely if there is no other black pixel in row i or in column j. Constraints: 1 <= m, n <= 200.

💡 Core Algorithmic Approaches

  1. Precompute the black count of every row and every column.
  2. A pixel is lonely exactly when its row count is 1 and its column count is 1 -- the pixel itself accounts for both.
  3. Then scan the picture once more and count the black pixels satisfying both conditions.
  4. This is O(m * n) and avoids the naive per-pixel scan of its whole row and column, which would be O(m * n * (m + n)).

💻 Benchmark Python3 Implementation

class Solution:
    def findLonelyPixel(self, picture: List[List[str]]) -> int:
        m, n = len(picture), len(picture[0])
        row = [0] * m
        col = [0] * n
        for i in range(m):
            for j in range(n):
                if picture[i][j] == "B":
                    row[i] += 1
                    col[j] += 1
        res = 0
        for i in range(m):
            for j in range(n):
                if picture[i][j] == "B" and row[i] == 1 and col[j] == 1:
                    res += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m * n): two passes over the grid with constant work per cell.
💾 Space Complexity
O(m + n) for the row and column counts.

⚠️ Interview Pitfalls & Follow-ups

  • Scanning the row and column for every black pixel: O(m * n * (m + n)) and much more code.
  • Requiring row[i] == 0: the pixel itself is black, so its row count is at least 1; the threshold is exactly 1.
  • Counting the pixel twice: a lonely pixel is counted once, and the row[i] == 1 and col[j] == 1 condition already implies uniqueness in both directions.
  • Assuming the picture is square: use separate m and n.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems