Solution For Dot Product Of Two Sparse Vectors
Problem:
Given two sparse vectors A and B, return the dot product of them.
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 Sparse vectors.
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:
For the first vector: [1,0,0,2,3], it can be represented as sparse vector:
0 –> 1
3 –> 2
4 –> 3
For the second vector: [0,3,0,4,0], it can be represented as sparse vector:
1 –> 3
3 –> 4
The dot product of two sparse vectors is defined as: return the dot product of A and B, which is A[0] * B[0] + A[1] * B[1] + … + A[n] * B[n] where n is the length of A and B where A[i] and B[i] are the ith elements of A and B, respectively.
Solution:
The basic idea here is to use hashmaps to store the sparse vectors.
We can create a hashmap to store the positions and values of non-zero elements of a vector. For example, for the vector [1, 0, 0, 2, 3], the hashmap would be {0: 1, 3: 2, 4: 3}.
Once we have stored both the vectors in hashmaps, we can iterate over the keys of one hashmap, and check if the key exists in the other hashmap. If it does, we can add the product of values at that key in both hashmaps to the dot product variable.
Let’s see the code below:
class SparseVector:
def init(self, nums: List[int]):
self.sparse = {}
for i, num in enumerate(nums):
if num != 0:
self.sparse[i] = num
# Return the dotProduct of two sparse vectors
def dotProduct(self, vec: 'SparseVector') -> int:
res = 0
for k in self.sparse.keys():
if k in vec.sparse:
res += self.sparse[k] * vec.sparse[k]
return res
First, we define the SparseVector class and initialize the init method which takes the input list as nums and stores the indices and values of non-zero elements in a dictionary.
Then, we create the dotProduct method to calculate the dot product of two sparse vectors. We iterate over the keys of one hashmap (in this case self.sparse.keys()), and check if the key exists in the other hashmap (in this case the argument vec.sparse). If it does, we add the product of values at that key in both hashmaps to the dot product variable. Finally, we return the dot product.
Step by Step Implementation For Dot Product Of Two Sparse Vectors
/**
* This is the solution for the leetcode problem "Dot Product of Two Sparse Vectors"
*
* The problem is as follows:
* Given two sparse vectors, compute their dot product.
* Implement class SparseVector such that the following code works:
*
* SparseVector v1 = new SparseVector(nums1);
* SparseVector v2 = new SparseVector(nums2);
* return v1.dotProduct(v2);
*
* Follow up: What if only one of the vectors is sparse?
*/
/**
* This is the solution for the leetcode problem "Dot Product of Two Sparse Vectors"
*
* The problem is as follows:
* Given two sparse vectors, compute their dot product.
* Implement class SparseVector such that the following code works:
*
* SparseVector v1 = new SparseVector(nums1);
* SparseVector v2 = new SparseVector(nums2);
* return v1.dotProduct(v2);
*
* Follow up: What if only one of the vectors is sparse?
*/
public class SparseVector {
private Map map;
private int size;
public SparseVector(int[] nums) {
this.size = nums.length;
this.map = new HashMap<>();
for (int i = 0; i < size; i++) {
if (nums[i] != 0) {
map.put(i, nums[i]);
}
}
}
// Return the dotProduct of two sparse vectors
public int dotProduct(SparseVector vec) {
if (this.size != vec.size) {
throw new IllegalArgumentException("The two vectors don't have the same size!");
}
int sum = 0;
for (Map.Entry entry : map.entrySet()) {
int index = entry.getKey();
int val1 = entry.getValue();
int val2 = vec.map.getOrDefault(index, 0);
sum += val1 * val2;
}
return sum;
}
} def dotProduct(self, A, B):
# write your code here
ans = 0
i, j = 0, 0
while i < len(A) and j < len(B):
if A[i][0] == B[j][0]:
ans += A[i][1] * B[j][1]
i += 1
j += 1
elif A[i][0] < B[j][0]:
i += 1
else:
j += 1
return ans// This function calculates the dot product of two sparse vectors.
function dotProduct(vector1, vector2) {
// Initialize result
var result = 0;
// Loop through each element in vector1
for (var i = 0; i < vector1.length; i++) {
// If the current element is not 0
if (vector1[i] !== 0) {
// Loop through each element in vector2
for (var j = 0; j < vector2.length; j++) {
// If the current element is not 0
if (vector2[j] !== 0) {
// If the indices of the two elements match
if (i === j) {
// Add the product of the two elements to the result
result += vector1[i] * vector2[j];
}
}
}
}
}
// Return the result
return result;
}#include#include using namespace std; class SparseVector { public: int size; vector elements; SparseVector(int n) { this->size = n; } void set(int i, int value) { if (i < 0 || i >= size) return; elements.push_back(i); elements.push_back(value); } int get(int i) { if (i < 0 || i >= size) return 0; for (int j = 0; j < elements.size(); j += 2) { if (elements[j] == i) return elements[j+1]; } return 0; } int dotProduct(SparseVector& other) { int result = 0; int i = 0, j = 0; while (i < elements.size() && j < other.elements.size()) { if (elements[i] == other.elements[j]) { result += elements[i+1] * other.elements[j+1]; i += 2; j += 2; } else if (elements[i] < other.elements[j]) { i += 2; } else { j += 2; } } return result; } };
using System;
public class SparseVector
{
private readonly int[] _sparseVector;
public SparseVector(int[] nums)
{
_sparseVector = nums;
}
// Return the dotProduct of two sparse vectors
public int DotProduct(SparseVector vec)
{
if (vec == null)
throw new ArgumentNullException(nameof(vec));
if (_sparseVector.Length != vec._sparseVector.Length)
throw new ArgumentException("The vectors do not have the same length.");
int result = 0;
for (int i = 0; i < _sparseVector.Length; i++)
{
result += _sparseVector[i] * vec._sparseVector[i];
}
return result;
}
}