LC 1570: Dot product of two sparse vectors

"""
Trade offs of using pairs vs hashmap: using simple list of pairs avoids
the complexity and overhead that comes with hashing. Dicts have internal overhead since hash tables need to store keys and handle collisions. ordered
pairs use less memory than hashmap for very sparse vector

Time complexity: let L1 and L2 be the number of non-zero elements in each
of the paits. Then the TC is O(L1 + L2). Notice with hashmap based approach
So time is also O(min(n, m)) on average, but can degrade with hash collisions.

Space complexity: O(L) for creating the index value pairs (not O(l1+l2))
"""

class SparseVector:
    def __init__(self, nums: List[int]):
        self.pairs = []
        for i in range(len(nums)):
            if nums[i]!=0:
                self.pairs.append([i, nums[i]])

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        i, j = 0, 0
        product = 0
        pairs_b = self.pairs
        pairs_a = vec.pairs
        if len(pairs_a) > len(pairs_b):
            return vec.dotProduct(self)

        while i < len(pairs_a) and j < len(pairs_b):
            if pairs_a[i][0] < pairs_b[j][0]:
                i += 1
            elif pairs_a[i][0] > pairs_b[j][0]:
                j += 1
            else:
                product += pairs_a[i][1]*pairs_b[j][1]
                i += 1
                j += 1

        return product

"""
In case of binary search, if we have a vector which is largely very
sparse and the other one not so much it would make sense to run
binary search

Time complexity: let n and me be the number of non-zero elements in the
small and large vectors. such that n<<m, in that case we would like
to iterate over the the n and search over the bigger m. < nlog(m) >
Space complexity: O(n)
"""

class SparseVector:
    def __init__(self, nums: List[int]):
        self.pairs = []
        for i in range(len(nums)):
            if nums[i]!=0:
                self.pairs.append([i, nums[i]])

    @staticmethod
    def find_target(index, pairs):

        left = 0
        right = len(pairs)-1

        while (left<=right):
            mid = (left+right)//2
            if pairs[mid][0] == index:
                return mid
            elif pairs[mid][0] < index:
                left = mid + 1
            else:
                right = mid - 1
        return -1

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:

        # iterate over the vector number pairs instead
        if len(vec.pairs) < len(self.pairs):
            return vec.dotProduct(self)

        n = len(self.pairs)
        m = len(vec.pairs)
        product = 0

        for index, value in self.pairs:
            # find target value
            target_index = SparseVector.find_target(index, vec.pairs)
            if target_index != -1:
                product += value*vec.pairs[target_index][1]

        return product