Given two sparse vectors, compute their dot product.
Implement class SparseVector:
SparseVector(nums) Initializes the object with the vector numsdotProduct(vec) Compute the dot product between the instance of SparseVector and vecA 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?
Example 1:
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:
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:
Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4] Output: 6
Constraints:
n == nums1.length == nums2.length1 <= n <= 10^50 <= nums1[i], nums2[i] <= 100We use a hash map d to store non-zero elements, where the key is the index, and the value is the corresponding value. We iterate through nums, and if nums[i] is not 0, we add (i, nums[i]) to the hash map d.
When calculating the dot product, we iterate through the hash map with fewer non-zero elements and check if the other hash map contains the corresponding key. If it exists, we multiply the corresponding values and add them to the result.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array.
Java
C++
Go
TypeScript
Rust
DOT PRODUCT OF TWO SPARSE VECTORS - 3 SOLUTIONS EXPLAINED [PYTHON] • Cracking FAANG • 14,270 views views
Watch 9 more video solutions →Practice Dot Product of Two Sparse Vectors with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor