class Solution {
public:
int findBlackPixel(vector<vector<char>>& picture, int N) {
int m = picture.size();
if(!m) return 0;
int n = picture[0].size();
if(!n) return 0;
vector<int> rows(m,0), cols(n,0);
unordered_map<string,int> um;
vector<string> srows;
for(int i = 0; i < m; ++i){
string s;
for(int j = 0; j < n; ++j){
if(picture[i][j] == 'B'){
rows[i]++;
cols[j]++;
}
s.push_back(picture[i][j]);
}
um[s]++;
srows.push_back(s);
}
int res = 0;
for(int i = 0; i < m; ++i)
if(rows[i] == N && um[srows[i]] == N)
for(int j = 0; j < n; ++j)
if(picture[i][j] == 'B' && cols[j] == N) ++res;
return res;
}
};;
O(mn) concise solution, C++


@i9r0k What's the complexity of
um[srows[i]]
? Doesn't that cause another factorn
in the complexity, assrows[i]
has to be compared with the existing key?I think for O(mn) you should do it like this:
for(int i = 0; i < m; ++i) if(rows[i] == N && um[srows[i]] == N) for(int j = 0; j < n; ++j) if(picture[i][j] == 'B' && cols[j] == N) ++res;
