1570. Dot Product of Two Sparse Vectors - Detailed Explanation

Problem Statement

You are required to implement a data structure for a sparse vector and then compute the dot product of two such sparse vectors. A sparse vector is one in which most elements are zero. The goal is to efficiently compute the dot product by taking advantage of the sparsity, rather than iterating over every element.

The dot product of two vectors v and w is defined as:

  v · w = ∑ (v[i] * w[i])

for all valid indices i. When most of the elements are zero, iterating only over the non-zero elements can lead to significant performance improvements.

Examples

Example 1

• Input: nums1 = [1, 0, 0, 2, 3], nums2 = [0, 3, 0, 4, 0]
• Explanation:
  For nums1, non-zero entries are at indices 0, 3, and 4 (with values 1, 2, and 3 respectively).
  For nums2, non-zero entries are at indices 1 and 3 (with values 3 and 4 respectively).
  The only overlapping non-zero index is 3, so the dot product is:

  2 * 4 = 8

• Output: 8

Example 2

• Input: nums1 = [0, 0, 0], nums2 = [0, 0, 0]

• Explanation:
  Since all elements are zero, the dot product is 0.

• Output: 0

Approaches

There are several ways to compute the dot product of two sparse vectors:

1. Naive Approach

• Idea:
  Iterate over every element (from index 0 to n–1) of both vectors, multiply corresponding elements, and sum them.
• Drawback:
  This approach runs in O(n) time regardless of sparsity, which is inefficient when n is large and most elements are zero.

2. Sparse Representation Using a Hash Map or List

• Idea:
  Store only the non-zero elements along with their indices. Then, iterate only over the non-zero elements of one vector and check if the corresponding index exists in the other vector.
• Pros:
  • Only processes non-zero entries.
  • Time complexity depends on the number of non-zero entries rather than the total length.
• Cons:
  Requires extra storage for the sparse representation.

3. Two-Pointer Technique on Sorted Lists

• Idea:
  Store non-zero elements in sorted order (by index) and then use a two-pointer approach to simultaneously traverse the non-zero lists of both vectors.
• Pros:
  • Efficient if both vectors are very sparse.
  • No extra overhead of hash lookups.
• Cons:
  • Requires both lists to be sorted by index (which is typically the case when processing in order).

In this explanation, we will focus on the sparse representation using a hash map (or dictionary) since it is straightforward to implement and works efficiently for sparse data.

Step-by-Step Walkthrough

1. Sparse Vector Initialization:

   • In the constructor, iterate through the input array.
   • For each index, if the element is non-zero, store the index and value in a hash map (or dictionary).

2. Dot Product Calculation:

   • When computing the dot product, iterate through the non-zero entries of the vector that has fewer non-zero elements (to minimize iterations).
   • For each non-zero entry (index, value) in the chosen vector, check if the other vector has a non-zero value at the same index.
   • If yes, multiply the two values and add the result to the dot product sum.

3. Return the Result:

   • After processing the non-zero elements, return the accumulated sum.

Python Code