Dot Product of Two Sparse Vectors - Solution & Explanation

Problem Overview: You receive two vectors that mostly contain zeros. Instead of storing every element, you design a sparse vector structure and implement a function that returns the dot product between two such vectors.

Approach 1: Direct Array Iteration (O(n) time, O(1) space)

The straightforward solution iterates through both vectors and multiplies values at the same index. Maintain a running sum: result += nums1[i] * nums2[i]. This works because the dot product is defined as the sum of element‑wise products. The drawback is wasted work when most values are zero. You still process every index even if the product contributes nothing. This approach is acceptable when vectors are dense or when the input is already stored as full arrays.

Approach 2: Hash Map Sparse Representation (O(k1 + k2) time, O(k1 + k2) space)

A sparse vector only needs to store non‑zero values. During initialization, iterate through the array and insert (index → value) pairs into a hash table whenever the value is not zero. If the vector contains k non‑zero elements, the storage shrinks from O(n) to O(k).

To compute the dot product, iterate through the smaller map and check whether the same index exists in the other map. Each lookup is O(1) on average. If both vectors contain a non‑zero value at index i, multiply them and add to the result. Zero entries never appear in the map, so they are skipped automatically.

This design drastically reduces work when the vectors are sparse. Instead of scanning the entire array length n, you only process indices that matter. The runtime becomes proportional to the number of stored elements rather than the vector size.

Some implementations also keep non‑zero entries sorted and use a two pointers technique to traverse both lists simultaneously. Both methods rely on the same core idea: ignore zero values and operate only on meaningful entries.

Recommended for interviews: The sparse hash map design is what interviewers expect. Start by explaining the naive array scan to show understanding of the dot product definition. Then optimize by storing only non‑zero values. This demonstrates awareness of sparse data structures, practical memory optimization, and efficient lookup using a hash table.