We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Dot Product of Two Sparse Vectors

Number: 1713

Difficulty: Medium

Paid? Yes

Companies: Meta, Bloomberg, Nvidia, Amazon, LinkedIn

Problem Description

Given two sparse vectors, compute their dot product. Design a SparseVector class that efficiently stores only the non-zero values along with their indices from the input vector. Then, implement a dotProduct method that computes the dot product between the instance vector and another SparseVector.

Key Insights

  • Store only non-zero elements of the vector along with their indices to save space.
  • Use a dictionary (or list of pairs) for fast lookup of non-zero elements.
  • While computing the dot product, iterate only over non-zero elements of one vector and check if the corresponding index exists in the other vector.
  • This approach is especially efficient if one or both vectors are sparse.

Space and Time Complexity

Time Complexity: O(k), where k is the number of non-zero elements in the smaller vector. Space Complexity: O(n) in the worst-case scenario (if the vector is not very sparse), but typically proportional to the number of non-zero elements.

Solution

We store the vector in a dictionary where keys are the indices with non-zero values and values are the actual non-zero values to save space. To calculate the dot product between two SparseVector instances, iterate over the non-zero entries of one vector and for each index, multiply it with the corresponding value in the other vector if that index exists. This reduces unnecessary multiplications with zeros and optimizes performance when dealing with sparse data.

Code Solutions

# Python implementation of SparseVector with detailed comments

class SparseVector:
    def __init__(self, nums):
        # Store only non-zero elements with their indices
        self.non_zero = {i: num for i, num in enumerate(nums) if num != 0}
    
    def dotProduct(self, vec):
        result = 0
        # Iterate over non-zero elements of self
        # To optimize, iterate over the smaller dictionary if needed
        for i, val in self.non_zero.items():
            # Multiply if the same index exists in vec.non_zero
            if i in vec.non_zero:
                result += val * vec.non_zero[i]
        return result

# Example usage:
# v1 = SparseVector([1,0,0,2,3])
# v2 = SparseVector([0,3,0,4,0])
# print(v1.dotProduct(v2))  # Output: 8
← Back to All Questions