Problem

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

  • SparseVector(nums) Initializes the object with the vector nums
  • dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

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

Examples

Example 1:

1
2
3
4

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

1
2
3
4

Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

1
2

Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6

Constraints:

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= 100

Solution

Method 1 – Hash Map Storage and Efficient Dot Product

Intuition

Since most elements are zero, we can store only the non-zero elements using a hash map (dictionary) of index to value. For the dot product, we iterate over the smaller map and sum the products where indices match, which is efficient for sparse vectors.

Approach

  1. In the constructor, store the non-zero elements as a map from index to value.
  2. For dot product, iterate over the smaller map and for each index, if it exists in the other vector, multiply and add to the result.
  3. This approach is efficient for sparse vectors and works for the follow-up as well.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class SparseVector {
    private Map<Integer, Integer> map;
    public SparseVector(int[] nums) {
        map = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) map.put(i, nums[i]);
        }
    }
    public int dotProduct(SparseVector vec) {
        int ans = 0;
        Map<Integer, Integer> m1 = this.map, m2 = vec.map;
        if (m1.size() > m2.size()) {
            Map<Integer, Integer> tmp = m1; m1 = m2; m2 = tmp;
        }
        for (int i : m1.keySet()) {
            if (m2.containsKey(i)) ans += m1.get(i) * m2.get(i);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class SparseVector:
    def __init__(self, nums: list[int]):
        self.map: dict[int, int] = {i: v for i, v in enumerate(nums) if v != 0}
    def dotProduct(self, vec: 'SparseVector') -> int:
        ans = 0
        if len(self.map) > len(vec.map):
            m1, m2 = vec.map, self.map
        else:
            m1, m2 = self.map, vec.map
        for i, v in m1.items():
            if i in m2:
                ans += v * m2[i]
        return ans

Complexity

  • ⏰ Time complexity: O(L), where L is the number of non-zero elements in the smaller vector.
  • 🧺 Space complexity: O(L), for storing the non-zero elements.