Dot Product of Two Sparse Vectors

Leetcode 1570. Dot Product of Two Sparse Vectors

Problem

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

Source: Leetcode 1570. Dot Product of Two Sparse Vectors

Solution

We can simply multiply the two vectors. But that’s not what is wanted here. This is not efficient since a zero element multiplied with some other value from other vector will result zero. So, we need to multiply only non-zero values from both the vectors.

To do this efficiently, we can use a map to keep track of non-zero values from one vector and then for the other vector, we can discard the zeros and multiply only non-zero values with the first vector. To keep track of nonzero from the first vector, we will use a map.

C++ Code

class SparseVector {
public:
    vector<int> arr;
    map<int, int> m;
    
    SparseVector(vector<int> &nums) {
        arr = nums;
        for(int i = 0; i < nums.size(); i++){
            if(nums[i] != 0)
                m[i] = nums[i];
        }
    }
    
    // Return the dotProduct of two sparse vectors
    int dotProduct(SparseVector& vec) {
        int result = 0;
        for(int i = 0; i < vec.arr.size(); i++){
            if(vec.arr[i] == 0)
                continue;
            if(m.find(i) != m.end())
                result += m[i] * vec.arr[i];
        }
        return result;
    }
};

// Your SparseVector object will be instantiated and called as such:
// SparseVector v1(nums1);
// SparseVector v2(nums2);
// int ans = v1.dotProduct(v2);

Conclusion

Hope you understood the problem and solution. There are other problems listed below, check them out! Also please write your comment for any feedback you want to share with us. Happy Coding! 🙂