1570. Dot Product of Two Sparse Vectors

 Given two sparse vectors, compute their dot product.

Implement class SparseVector:

• SparseVector(nums) Initializes the object with the vector nums
• dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

 

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6

 

Constraints:

• n == nums1.length == nums2.length
• 1 <= n <= 10^5
• 0 <= nums1[i], nums2[i] <= 100

==============

class SparseVector {

public:

    vector<pair<int,int>> data_;

    vector<pair<int, int>> populate(vector<int>& nums) {

        vector<pair<int,int>> data;

        for (int i = 0; i < nums.size(); i++) {

            if (nums[i] != 0) {

                data.push_back({i, nums[i]});

            }

        }

        return data;

    }

    

    /*

       {{1, 5}, {6, 2}, {19, 2}, {50, 9}}

       {{2, 5}, {4, 2}, {6, 2}, {19, 9}, {29, 8}, {50, 9}, {51, 2}}

    */

    

    int dotProd(vector<pair<int,int>>& data_2_) {

        int size1 = data_.size();

        int size2 = data_2_.size();

        

        int iter1 = 0, iter2 = 0;

        int sum = 0;

        while (iter1 < size1 && iter2 < size2) {

            if (data_[iter1].first < data_2_[iter2].first) {

                iter1++;

            } else if (data_[iter1].first > data_2_[iter2].first) {

                iter2++;

            } else {

                sum += data_[iter1].second * data_2_[iter2].second;

                iter1++;

                iter2++;

            }

        }

        return sum;

    }

    

    SparseVector(vector<int> &nums) {

        data_ = populate(nums);

    }

    

    // Return the dotProduct of two sparse vectors

    int dotProduct(SparseVector& vec) {

        return dotProd(vec.data_);

    }

};

// Your SparseVector object will be instantiated and called as such:

// SparseVector v1(nums1);

// SparseVector v2(nums2);

// int ans = v1.dotProduct(v2);