LeetCode 1570: Dot Product of Two Sparse Vectors
LeetCode 1570 Solution Explanation
Explanation
To compute the dot product of two sparse vectors efficiently, we can store only the non-zero elements of the vectors along with their indices. Then, we can iterate over these non-zero elements and multiply the corresponding elements from both vectors. Finally, we sum up these products to get the dot product.
The time complexity of this approach is O(n) where n is the number of non-zero elements in the vectors, as we only iterate over the non-zero elements. The space complexity is also O(n) to store the non-zero elements and their indices.
LeetCode 1570 Solutions in Java, C++, Python
class SparseVector {
Map<Integer, Integer> map;
SparseVector(int[] nums) {
map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
map.put(i, nums[i]);
}
}
}
public int dotProduct(SparseVector vec) {
int product = 0;
for (int i : map.keySet()) {
if (vec.map.containsKey(i)) {
product += map.get(i) * vec.map.get(i);
}
}
return product;
}
}Interactive Code Editor for LeetCode 1570
Improve Your LeetCode 1570 Solution
Use the editor below to refine the provided solution for LeetCode 1570. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...