Simple C++ solution using single set: no maps/tables !

• ``````/* A(m x n) * B(n x p) = C(m x p) . The sparsity tell us this: If a row in A or
a col in B is 0, corresponding row or col is 0 in C. We store this info in set
with this trick:
if kth row in A is 0, we enter K+1 in set
if kth col in B is 0, we enter -(K+1) in set
This +1 business is because there is no -0 and +0 to discriminate between row/col
*/
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>> C(m, vector<int>(p, 0));
set<int> s;
for (int i = 0; i < m; i++) { // A's row scanning
int check = 0;
for (auto x : A[i])
check |= x;
if (!check)
s.insert(i+1);
}
for (int i = 0; i < p; i++) { // B's col scanning
int check = 0;
for (int j = 0; j < n; j++)
check |= B[j][i];
if (!check)
s.insert(-(i+1));
}
for (int i = 0; i < m; i++) {
if (s.find(i+1) != s.end())
continue;
for (int j = 0; j < p; j++) {
if (s.find(-(j+1)) != s.end())
continue;
for (int k = 0; k < n; k++) {
if (A[i][k] && B[k][j])
C[i][j] += A[i][k] * B[k][j];
}
}
}
return C;
}
``````

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