⚡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

中文速览与面试要点

孤独像素 I

给你一个大小为 m × n 的矩阵 picture,其中 "B" 表示黑色像素、 "W" 表示白色像素。请你统计其中「孤独的黑色像素」的数目。一个黑色像素是孤独的,当且仅当它所在的 行 和 列 中都恰好只有它这一个黑色像素。约束:m == picture.length;n == picture[i].length;1 ≤ m, n ≤ 500;picture[i][j] 为 "B" 或 "W"。

核心要点

  • 两遍扫描 + 行列计数(标准解) :第一遍遍历矩阵,统计每行的黑像素个数 rows[i] 与每列的黑像素个数 cols[j] 。
  • 第二遍判定 :再次遍历,若 picture[i][j] == "B" 且 rows[i] == 1 且 cols[j] == 1 ,则计数加一。
  • 为什么不能一遍完成 :判定 (i, j) 是否为孤独像素需要该行与该列的 完整 信息,而单次遍历时行列信息尚未收集完整。
  • 空间优化 :行列计数数组大小分别为 m 与 n,是本题的最小必要开销。

常见陷阱

  • 只统计行或只统计列 :孤独像素要求 行列同时 满足条件,只判断一个方向会大量误计。
  • 一遍扫描就尝试判定 :遍历到 (i, j) 时该行该列的后续像素还没看过,判定必然不准确。必须两遍。
  • 误以为「孤独」是指周围 8 格没有黑像素 :题目定义是 整行整列 只有它一个,与邻域无关。这是常见的题意误解。

参考实现

class Solution:
    def findLonelyPixel(self, picture: list[list[str]]) -> int:
        m, n = len(picture), len(picture[0])
        rows = [0] * m
        cols = [0] * n
        for i in range(m):
            for j in range(n):
                if picture[i][j] == 'B':
                    rows[i] += 1
                    cols[j] += 1
        count = 0
        for i in range(m):
            for j in range(n):
                if picture[i][j] == 'B' and rows[i] == 1 and cols[j] == 1:
                    count += 1
        return count