Leetcode 1570: Dot Product of Two Sparse Vectors

Hash table for sparse vector representation

Problem description

Tricks summary

• More efficient representation of sparse vectors: We use a hash table whose key and value are non-zero elements’ index and value, respectively. This immediately reduces the size of the iterator, and as a result, time and space complexity could both be below O(n)
• Use vector with fewer non-zero elements as the lead iterator to compute dot product more efficiently: We iterate through the shorter hash table and check if the same index exists in the other hash table. If it does, multiply the two non-zero values and add to the result

Python solution

Putting these together, we obtain the following solution:

from typing import List


class SparseVector:
    def __init__(self, nums: List[int]):
        # Use hash table to store index and value of non-zero elements
        self.non_zeros = {
            index: num for index, num in enumerate(nums) if num != 0
        }

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: "SparseVector") -> int:
        # Always lead with the hash map with fewer number of non-zero elements
        #   If inherent orders violate this rule, flip the order
        #   by calling the method with flipped instanced order as shown below
        if len(self.non_zeros) > len(vec.non_zeros):
            return vec.dotProduct(self)

        # Dot product: sum on generator
        return sum(
            self.non_zeros[index] * vec.non_zeros.get(index, 0)
            for index in self.non_zeros
        )


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

Space and time complexity

With n denote vector length:

• Space complexity: O(n) — In worst case scenario when neither vectors is sparse, we need O(n) space for the hash table that stores non-zero elements
• Time complexity: O(n) —

1. O(n) when creating hash table: We need to iterate through both vectors once when creating the hash tables
2. O(k) for dot product operation, where k = minimum amount of non-zero entries

Collectively we have time complexity of O(n)

Unit test examples (with pytest)

def test_sparse_vector_dot_product():
    vec1 = SparseVector([1, 0, 0, 2, 3])
    vec2 = SparseVector([0, 3, 0, 4, 0])

    # Test with two different vectors
    assert vec1.dotProduct(vec2) == 8

    # Test with a vector and itself
    assert vec1.dotProduct(vec1) == 14