LeetCode Solutions
531. Lonely Pixel I
Time: $O(mn)$ Space: $O(m + n)$
class Solution {
public:
int findLonelyPixel(vector<vector<char>>& picture) {
const int m = picture.size();
const int n = picture[0].size();
int ans = 0;
vector<int> rows(m); // rows[i] := # of Bs in rows i
vector<int> cols(n); // cols[i] := # of Bs in cols i
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (picture[i][j] == 'B') {
++rows[i];
++cols[j];
}
for (int i = 0; i < m; ++i)
if (rows[i] == 1) // Only have to examine the rows when rows[i] == 1
for (int j = 0; j < n; ++j)
// After we met the 'B' in this rows, we break and search the next row
if (picture[i][j] == 'B') {
if (cols[j] == 1)
++ans;
break;
}
return ans;
}
};
class Solution {
public int findLonelyPixel(char[][] picture) {
final int m = picture.length;
final int n = picture[0].length;
int ans = 0;
int[] rows = new int[m]; // rows[i] := # of Bs in rows i
int[] cols = new int[n]; // cols[i] := # of Bs in cols i
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (picture[i][j] == 'B') {
++rows[i];
++cols[j];
}
for (int i = 0; i < m; ++i)
if (rows[i] == 1) // Only have to examine the rows when rows[i] == 1
for (int j = 0; j < n; ++j)
// After we met the 'B' in this rows, we break and search the next row
if (picture[i][j] == 'B') {
if (cols[j] == 1)
++ans;
break;
}
return ans;
}
}
class Solution:
def findLonelyPixel(self, picture: List[List[str]]) -> int:
m = len(picture)
n = len(picture[0])
ans = 0
rows = [0] * m # rows[i] := # Of Bs in rows i
cols = [0] * n # cols[i] := # Of Bs in cols i
for i in range(m):
for j in range(n):
if picture[i][j] == 'B':
rows[i] += 1
cols[j] += 1
for i in range(m):
if rows[i] == 1: # Only have to examine the rows when rows[i] == 1
for j in range(n):
# After we met the 'B' in this rows, we break and search the next row
if picture[i][j] == 'B':
if cols[j] == 1:
ans += 1
break
return ans