Problem
Given two sparse vectors, compute their dot product.
Implement class SparseVector
:
SparseVector(nums)
Initializes the object with the vectornums
dotProduct(vec)
Compute the dot product between the instance of SparseVector andvec
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:
|
|
Example 2:
|
|
Example 3:
|
|
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
- In the constructor, store the non-zero elements as a map from index to value.
- 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.
- This approach is efficient for sparse vectors and works for the follow-up as well.
Code
|
|
|
|
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.