O(mn) concise solution, C++

• ``````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;
}
};;
``````

• @i9r0k What's the complexity of `um[srows[i]]`? Doesn't that cause another factor `n` in the complexity, as `srows[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;``````

• @StefanPochmann Good point. Corrected.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.