1570. Dot Product of Two Sparse Vectors

Problem Statement

link: LeetCode.cn LeetCode 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:

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

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

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

Solution Approach

The SparseVector class efficiently computes the dot product of two sparse vectors by storing only non-zero elements and iterating over the sparse representation, ensuring optimized time and space complexity.

Algorithm

1. Initialization with Non-Zero Elements: The SparseVector class initializes by storing only the non-zero elements of the vector in a dictionary (self.nonzeros), mapping indices to their values.
2. Efficient Dot Product Calculation: To compute the dot product, the dotProduct method iterates through the non-zero elements of the current vector and checks if the indices exist in the other vector’s dictionary, multiplying corresponding values and summing the results.
3. Handling Large Vectors: This approach efficiently handles large vectors with mostly zero values by avoiding operations on zero elements and focusing only on the significant non-zero elements for the dot product calculation.

   Complexity

   time complexity: O(n) space complexity: O(n)

Implement

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

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        result = 0
        for i, n in self.nonzeros.items():
            if i in vec.nonzeros:
                result += n * vec.nonzeros[i]
        return result
        

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

    
    

Twitter  facebook  Email