# C++ Straight Forward method

• First scan the two matrix to find the index of non-zeros entries, push these entries to vector.
When computing the result, just consider

1. when index equal, then increment both index

2. otherwise increment smaller index

vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {

`````` int am = A.size();//2
int bm = B.size();//3
//if(!am || !bm)
//    return result;
int an = A[0].size();//3
int bn = B[0].size();//3 2*3 3*3 => 2*3
vector<vector<int>> result(am,vector<int>(bn,0));
vector<vector<int>> A_non_zero(am);
vector<vector<int>> B_non_zero(bn);
//an == bm
for(int i=0;i<am;i++)
for(int j=0;j<an;j++)
if(A[i][j])A_non_zero[i].push_back(j);

for(int j=0;j<bn;j++)
for(int i=0;i<bm;i++)
if(B[i][j])B_non_zero[j].push_back(i);

for(int i=0;i<am;i++)
for(int j=0;j<bn;j++){
int m=0,n=0;
while(m<A_non_zero[i].size() && n<B_non_zero[j].size()){
int idx_A = A_non_zero[i][m];
int idx_B = B_non_zero[j][n];
if(idx_A == idx_B){
result[i][j]+= (A[i][idx_A]*B[idx_B][j]);
m++;
n++;
}
else if(idx_A > idx_B)
n++;
else
m++;
}
}
return result;
``````
``}``

• Thanks! Here's a solution with one hash table for B alone.

``````class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
vector<vector<int>> out(A.size(), vector<int>(B[0].size(), 0));
unordered_map<int, vector<int>> BNonZeroIndexes;

for(int i = 0; i < B.size(); i++) {
BNonZeroIndexes[i] = {};
for(int k = 0; k < B[0].size(); k++) {
if(B[i][k])  BNonZeroIndexes[i].push_back(k);
}
}

for(int i = 0; i < A.size(); i++) {
for(int k = 0; k < A[0].size(); k++) {
if(A[i][k] != 0) {
for(int j : BNonZeroIndexes[k]) { //In Row K, Iterate only over indexes that has non-zero values.
out[i][j] += A[i][k] * B[k][j];
}
}
}
}

return out;
}
};
``````

• One vector<vector<int>> for B will be sufficient and better than hash table.

``````class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
int m = A.size(), n = A[0].size(), p = B[0].size();
vector<vector<int>> mtxB(n, vector<int>());
for (int i = 0; i < n; ++i) {
for (int j = 0; j < p; ++j) {
if (B[i][j] != 0) mtxB[i].push_back(j);
}
}
vector<vector<int>> ans(m, vector<int>(p, 0));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (A[i][j] != 0) {
for (int k: mtxB[j]) {
ans[i][k] += A[i][j]*B[j][k];
}
}
}
}
return ans;
}
};
``````

We can further optimize the code using only one vector<int>. See below.

``````class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
int m = A.size(), n = A[0].size(), p = B[0].size();
vector<vector<int>> ans(m, vector<int>(p, 0));
for (int j = 0; j < n; ++j) {
// working on colume j of A and row j of B
vector<int> rowB;
for (int i = 0; i < p; ++i)
if (B[j][i]) rowB.push_back(i);
for (int i = 0; i < m; ++i) {
if (A[i][j]) {
for (int k: rowB) {
ans[i][k] += A[i][j]*B[j][k];
}
}
}
}
return ans;
}
};
``````

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