Dot Product Of Two Sparse Vectors - Leetcode Solution

Problem:

Given two sparse vectors A and B, return the dot product of them.

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 Sparse vectors.

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: For the first vector: [1,0,0,2,3], it can be represented as sparse vector: 0 --> 1 3 --> 2 4 --> 3 For the second vector: [0,3,0,4,0], it can be represented as sparse vector: 1 --> 3 3 --> 4 The dot product of two sparse vectors is defined as: return the dot product of A and B, which is A[0] * B[0] + A[1] * B[1] + ... + A[n] * B[n] where n is the length of A and B where A[i] and B[i] are the ith elements of A and B, respectively.

Solution:

The basic idea here is to use hashmaps to store the sparse vectors.

We can create a hashmap to store the positions and values of non-zero elements of a vector. For example, for the vector [1, 0, 0, 2, 3], the hashmap would be {0: 1, 3: 2, 4: 3}.

Once we have stored both the vectors in hashmaps, we can iterate over the keys of one hashmap, and check if the key exists in the other hashmap. If it does, we can add the product of values at that key in both hashmaps to the dot product variable.

Let’s see the code below:

class SparseVector: def init(self, nums: List[int]): self.sparse = {} for i, num in enumerate(nums): if num != 0: self.sparse[i] = num

# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
    res = 0
    for k in self.sparse.keys():
        if k in vec.sparse:
            res += self.sparse[k] * vec.sparse[k]
    return res
    
    

First, we define the SparseVector class and initialize the init method which takes the input list as nums and stores the indices and values of non-zero elements in a dictionary.

Then, we create the dotProduct method to calculate the dot product of two sparse vectors. We iterate over the keys of one hashmap (in this case self.sparse.keys()), and check if the key exists in the other hashmap (in this case the argument vec.sparse). If it does, we add the product of values at that key in both hashmaps to the dot product variable. Finally, we return the dot product.

1