# Standard hash table solution 36ms in C++

• ``````typedef pair<pair<int,int>,int> pos_val;
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
if(A.empty()||A[0].empty()||B[0].empty()) return vector<vector<int>>();
vector<pos_val> map_A,map_B; //store nonzero values of A and B
int n=A.size(), m=B[0].size(),mid=B.size();
vector<vector<int>> C(n,vector<int>(m,0));
for(int i=0;i<n;++i){
for(int j=0;j<mid;++j){
if(A[i][j]!=0){
pos_val tmp(pair<int,int>(i,j),A[i][j]);
map_A.push_back(tmp);}
}
}
for(int i=0;i<mid;++i){
for(int j=0;j<m;++j){
if(B[i][j]!=0){
pos_val tmp(pair<int,int>(i,j),B[i][j]);
map_B.push_back(tmp);}
}
}
for(int i=0;i<map_A.size();++i){
for(int j=0;j<map_B.size();++j){
if(map_A[i].first.second==map_B[j].first.first)
C[map_A[i].first.first][map_B[j].first.second]+=map_A[i].second*map_B[j].second;
}
}

return C;

}
};``````

• @touzi

``````class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
if ( A.empty() || B.empty() ) return vector<vector<int>>();
vector< pair< pair<int, int>, int > > mapA, mapB;
int n = A.size(), m = A[0].size(), p = B[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if ( A[i][j] != 0 )
mapA.push_back( { {i, j}, A[i][j] } );
}
}
for (int k = 0; k < p; k++) {
for (int j = 0; j < m; j++) {
if ( B[j][k] != 0 )
mapB.push_back( { {j, k}, B[j][k] } );
}
}
vector<vector<int>> res(n, vector<int>(p, 0));
for (auto ha: mapA) {
for (auto hb: mapB) {
if (ha.first.second == hb.first.first)
res[ha.first.first][hb.first.second] += ha.second * hb.second;
}
}
return res;
}
};``````

• ``````typedef pair<pair<int,int>,int> pos_val;
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
if(A.empty()||A[0].empty()||B[0].empty()) return vector<vector<int>>();
vector<pos_val> map_A,map_B; //store nonzero values of A and B
int n=A.size(), m=B[0].size(),mid=B.size();
vector<vector<int>> C(n,vector<int>(m,0));
for(int i=0;i<n;++i){
for(int j=0;j<mid;++j){
if(A[i][j]!=0){
pos_val tmp(pair<int,int>(i,j),A[i][j]);
map_A.push_back(tmp);}
}
}
for(int i=0;i<mid;++i){
for(int j=0;j<m;++j){
if(B[i][j]!=0){
pos_val tmp(pair<int,int>(i,j),B[i][j]);
map_B.push_back(tmp);}
}
}
for(int i=0;i<map_A.size();++i){
for(int j=0;j<map_B.size();++j){
if(map_A[i].first.second==map_B[j].first.first)
C[map_A[i].first.first][map_B[j].first.second]+=map_A[i].second*map_B[j].second;
}
}

return C;

}
};
``````

Can someone explain how this is better than simply doing a check whether A[i][k] or B[k][J] is 0 in the innermost iteration of loops in the brute-force (traditional) matrix multiplication method?

``````  for(int i=0;i<map_A.size();++i){
for(int j=0;j<map_B.size();++j){
if(map_A[i].first.second==map_B[j].first.first)
C[map_A[i].first.first][map_B[j].first.second]+=map_A[i].second*map_B[j].second;
}
}
``````

This loop-nesting itself has worse complexity than brute-force approach. The size of map_A and map_B are n * mid and mid * m respectively, so the if statement within the loop itself is called n * m * mid * mid times and can have upto

``````n*m*mid*mid times
``````

many multiplications, which is worse than O(nm mid) multiplications in brute-force.

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