Table of Contents
Leetcode 1570. Dot Product of Two Sparse Vectors
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?
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
Source: Leetcode 1570. Dot Product of Two Sparse Vectors
Solution
We can simply multiply the two vectors. But that’s not what is wanted here. This is not efficient since a zero element multiplied with some other value from other vector will result zero. So, we need to multiply only non-zero values from both the vectors.
To do this efficiently, we can use a map to keep track of non-zero values from one vector and then for the other vector, we can discard the zeros and multiply only non-zero values with the first vector. To keep track of nonzero from the first vector, we will use a map.
C++ Code
class SparseVector { public: vector<int> arr; map<int, int> m; SparseVector(vector<int> &nums) { arr = nums; for(int i = 0; i < nums.size(); i++){ if(nums[i] != 0) m[i] = nums[i]; } } // Return the dotProduct of two sparse vectors int dotProduct(SparseVector& vec) { int result = 0; for(int i = 0; i < vec.arr.size(); i++){ if(vec.arr[i] == 0) continue; if(m.find(i) != m.end()) result += m[i] * vec.arr[i]; } return result; } }; // Your SparseVector object will be instantiated and called as such: // SparseVector v1(nums1); // SparseVector v2(nums2); // int ans = v1.dotProduct(v2);
Conclusion
Hope you understood the problem and solution. There are other problems listed below, check them out! Also please write your comment for any feedback you want to share with us. Happy Coding! 🙂
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you.
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you. 20bet
Hi foolishhungry.com owner, Thanks for the informative post!
Hi foolishhungry.com admin, You always provide great information and insights.
Dear foolishhungry.com administrator, Your posts are always well presented.
Hi foolishhungry.com admin, Your posts are always thought-provoking and inspiring.
Dear foolishhungry.com webmaster, Your posts are always well-written and engaging.
Hi foolishhungry.com admin, Your posts are always well structured and easy to follow.
Hi foolishhungry.com administrator, Your posts are always well-written and engaging.
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://www.binance.com/es/register?ref=V2H9AFPY
Very well presented. Every quote was awesome and thanks for sharing the content. Keep sharing and keep motivating others.
Hi foolishhungry.com admin, Your posts are always well organized and easy to understand.
Hi foolishhungry.com admin, You always provide useful links and resources.
Hello foolishhungry.com administrator, You always provide key takeaways and summaries.
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://www.binance.info/vi/join?ref=OMM3XK51
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me? https://accounts.binance.com/ar/register?ref=YY80CKRN
Dear foolishhungry.com administrator, Your posts are always well-supported and evidence-based.
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article.
Your point of view caught my eye and was very interesting. Thanks. I have a question for you.
Your point of view caught my eye and was very interesting. Thanks. I have a question for you.
Your article helped me a lot, is there any more related content? Thanks!
To the foolishhungry.com owner, Keep up the good work, admin!