C++ solution easy to understand


  • 0
    Q
    class Solution {
    public:
        vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
            if(A.size() == 0 || A[0].empty() || B.size() == 0 || B[0].empty() || A[0].size() != B.size())
                return vector<vector<int>> {};
            map<int,vector<pair<int,int>>> a,b;
            for(int i=0;i<A.size();i++){
                for(int j=0;j<A[0].size();j++)
                    if(A[i][j] != 0)
                        a[i].push_back(make_pair(A[i][j],j));
            }
            
            for(int i=0;i<B[0].size();i++){
                for(int j=0;j<B.size();j++)
                    if(B[j][i] != 0)
                        b[i].push_back(make_pair(B[j][i],j));
            }
            
            vector<vector<int>> res(A.size(),vector<int> (B[0].size()));
            
            for(int i=0;i<A.size();i++){
                for(int m=0;m<B[0].size();m++){
                    vector<pair<int,int>> ta,tb;
                    ta = a[i];
                    tb = b[m];
                    int j=0,k=0;
    
                    while(j<ta.size() && k<tb.size()){
                        if(ta[j].second > tb[k].second)
                            k++;
                        else if(ta[j].second < tb[k].second)
                            j++;
                        else
                            res[i][m] += ta[j++].first * tb[k++].first;
                    }
                }
            }
            return res;
        }
    };
    

Log in to reply
 

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