1570. Dot Product of Two Sparse Vectors

sparse matrix:

1. only store non-0 value so we can store less
1. to find product, there are 3 approaches
- hashmap (for unknown reason fb doesn't like this)
  - T = O(min(M, N)), Space = O(M + N)
- 2 pointers
  - T = O(M + N), Space = O(M + N)
- binary search: good when N is super large
  - T = O(M logN), Space = O(M + N)

2 pointers

class SparseVector:
    def __init__(self, nums: List[int]):
        self.index_to_num = []
        for i, num in enumerate(nums):
            if num != 0:
                self.index_to_num.append((i, num))

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

binary search

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

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: 'SparseVector') -> int:
        res = 0
        vec_index_list = list(vec.index_to_num.keys())
        for index, num in self.index_to_num.items():
            if self.binary_search(index, vec_index_list) != -1:
                res += num * vec.index_to_num[index]
        return res
    
    def binary_search(self, target_idx, index_list):
        low, high = 0, len(index_list)-1
        while low <= high:
            mid = low + (high - low) // 2
            if index_list[mid] == target_idx:
                return mid
            elif index_list[mid] < target_idx:
                low = mid + 1
            else:
                high = mid - 1
        
        return -1

1570. Dot Product of Two Sparse Vectors - cocoder39/coco39_LC GitHub Wiki