# C++ Solution using Hash Set

• ``````class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> ans;
if(!A.size() || !B.size())
return ans;
int n = A.size(), m = B[0].size(), m1 = A[0].size(), n1 = B.size();
ans.resize(n);
for(int i = 0; i < n; ++ i){
vector<int> tmp(m);
ans[i] = tmp;
}

vector<unordered_set<int>> mtx1(n), mtx2(m);
for(int i = 0; i < n; ++ i){
for(int j = 0; j < m1; ++ j){
if(A[i][j]){
mtx1[i].insert(j);
}
}
}
for(int i = 0; i < m; ++ i){
for(int j = 0; j < n1; ++ j){
if(B[j][i]){
mtx2[i].insert(j);
}
}
}

for(int i = 0; i < n; ++ i){
if(!mtx1[i].size())
continue;
for(int j = 0; j < m; ++ j){
int cnt = 0;
if(!mtx2[j].size())
continue;
unordered_set<int>::iterator it = mtx1[i].begin();
for(; it != mtx1[i].end(); ++ it){
if(mtx2[j].find(*it) != mtx2[j].end())
cnt += A[i][*it]*B[*it][j];
}
ans[i][j] = cnt;
}
}

return ans;
}
};``````

• I don’t think you will need the hash set. Just using vector<vector<int>> seems OK.

• Exactly, just used the kind of data structure u r familiar with.

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