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
- Precompute the black count of every row and every column.
- A pixel is lonely exactly when its row count is 1 and its column count is 1 -- the pixel itself accounts for both.
- Then scan the picture once more and count the black pixels satisfying both conditions.
- 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] == 1condition already implies uniqueness in both directions. - Assuming the picture is square: use separate
mandn.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 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