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


  • 0
    V
    /* 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;
        }
    

Log in to reply
 

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