unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 1570: Dot Product of Two Sparse Vectors

link

For two vectors \textbf{a} = \langle a_1, a_2, \ldots, a_n \rangle and \textbf{b} = \langle b_1, b_2, \ldots, b_n \rangle, the dot product \textbf{a} \bullet \textbf{b} = \sum_{i=1}^{n} \left( a_i \cdot b_i \right).

  • If a_i = 0 or b_i = 0, \left( a_i \cdot b_i \right) does not play a role in the dot product.
  • The order of sum does not matter.

So, we represent a sparse vector as a map of nonzero values: {index -> value}. While computing dot product, we iterate over the vector that has a shorter sparse representation.

Say len(nums) = n and only m values are nonzero.

OperationTimeSpace
__init__\mathcal{O}(n)\mathcal{O}(m)
dotProduct\mathcal{O}(m)\mathcal{O}(1)
class SparseVector:
    def __init__(self, nums: List[int]):
        self.data = {i: val for i, val in enumerate(nums) if val != 0}

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: "SparseVector") -> int:
        short_vec, long_vec = (
            (self.data, vec.data)
            if len(self.data) <= len(vec.data)
            else (vec.data, self.data)
        )
        
        dot = 0
        for i, elem in short_vec.items():
            if i in long_vec:
                dot += ( elem * long_vec[i] )
        
        return dot


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

Follow up: What if only one of the vectors is sparse?

We would still pick the sparse vector as the shorter of the two and iterate over it.

tanvirdotzaman

,

Leave a comment