A sparse matrix is a matrix in which most of the elements are zero
You store which row of matrix a and which column of matrix b have zero so we don’t need to compute these rows and columns
vector<vector<int>> multiply(vector<vector<int>> a, vector<vector<int>> b){
vector<vector<int>> ans(a.size(), vector<int>(b[0].size()));
vector<bool> rowA = vector<bool>(a.size(), false);
vector<bool> colB = vector<bool>(b[0].size(), false);
for(int i = 0; i < a.size(); i++)
for(int j = 0; j < a[0].size(); j++)
if(a[i][j] != 0){
rowA[i] = true;
break;
}
for(int i = 0; i < b.size(); i++)
for(int j = 0; j < b[0].size(); j++)
if(a[i][j] != 0){
colB[j] = true;
break;
}
for(int i = 0; i < a.size(); i++){
for(int k = 0; k < b[0].size(); k++){
if(!rowA[i] || !colB[k]){
ans[i][k] = 0;
continue;
}
int sum = 0;
for(int j = 0; j < a[0].size(); j++)
sum += a[i][j] * b[j][k];
ans[i][k] = sum;
}
}
return ans;
}
You have a 2d matrix and there are two queries
This is quite similar on 1d array with long implementation.