Saved from https://leetcode.com/problems/dot-product-of-two-sparse-vectors/

lc1570

class SparseVector:
    """
    Time: O(n) for __init__, O(L) for dotProduct
    Space: O(L), where L is the number of non-zero values
    """
    def __init__(self, nums: List[int]):
        self.values = []
        self.index = []
        for i in range(len(nums)):
            if nums[i] != 0:
                self.values.append(nums[i])
                self.index.append(i)

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        product = 0
        i, j = 0, 0
        while i < len(self.values) and j < len(vec.values):
            if vec.index[j] == self.index[i]:
                product += vec.values[j] * self.values[i]
                i += 1
                j += 1
            elif vec.index[j] < self.index[i]:
                j += 1
            else:
                i += 1
        return product
            

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