LeetCode [1570] Dot Product of Two Sparse Vectors

 1570. Dot Product of Two Sparse Vectors

Medium

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?

 

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.length
• 1 <= n <= 10^5
• 0 <= nums1[i], nums2[i] <= 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

class SparseVector { Map<Integer, Integer> map; SparseVector(int[] nums) { map = new HashMap<>(); for(int i=0; i<nums.length; ++i){ map.put(i, nums[i]); } } // Return the dotProduct of two sparse vectors public int dotProduct(SparseVector vec) { int sz1 = map.size(); int sz2 = vec.map.size(); if(sz1<sz2) return helper(map, vec.map); else return helper(vec.map, map); } int helper(Map<Integer, Integer> map1, Map<Integer, Integer> map2){ int s = 0; for(Map.Entry<Integer, Integer> en : map1.entrySet()){ int index = en.getKey(); int value = en.getValue(); if(map2.containsKey(index)){ s += value*map2.get(index); } } return s; } } // Your SparseVector object will be instantiated and called as such: // SparseVector v1 = new SparseVector(nums1); // SparseVector v2 = new SparseVector(nums2); // int ans = v1.dotProduct(v2);