Dot Product of Two Sparse Vectors
Dot Product of Two Sparse Vectors is a medium design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (index-value pairs + two pointers), runs in O(n) to build, O(k1 + k2) per product time and O(k) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (dense copy) up.
Problem
A sparse vector is one where most entries are zero. Design a class SparseVector that stores such a vector compactly and can compute its dot product with another SparseVector of the same length.
SparseVector(int[] nums)builds the vector from the arraynums.int dotProduct(SparseVector vec)returns the dot product of this vector andvec: the sum ofthis[i] * vec[i]over every indexi.
Choose a representation that does not waste work on the zero entries. As a follow-up, think about what changes when only one of the two vectors is sparse.
Examples
Example 1
- Input
nums1 = [0, 4, 0, 0, 2], nums2 = [3, 5, 0, 1, 0]- Output
20- Why
- Only index 1 is non-zero in both vectors: 4 * 5 = 20. Index 4 pairs 2 with 0 and adds nothing.
Example 2
- Input
nums1 = [7, 0, 0], nums2 = [0, 0, 9]- Output
0- Why
- The non-zero positions never overlap, so every product is 0.
Example 3
- Input
nums1 = [0, 2, 0, 3, 0, 0, 1], nums2 = [0, 6, 0, 0, 0, 0, 8]- Output
20- Why
- 2 * 6 + 1 * 8 = 12 + 8 = 20.
Constraints
n == nums1.length == nums2.length1 <= n <= 10^50 <= nums1[i], nums2[i] <= 100- The tests run
new SparseVector(nums1).dotProduct(new SparseVector(nums2)).
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (dense copy) | O(n) | O(n) |
| Hash map of non-zeros | O(n) to build, O(min(k1, k2)) per product | O(k) |
| Optimal (index-value pairs + two pointers) | O(n) to build, O(k1 + k2) per product | O(k) |
1Brute force (dense copy)
O(n)Every index is visited, even the zero ones.O(n)Each vector stores all n values, zeros included.Keep the whole array inside the object and multiply position by position. Simple, but it pays for every zero, which is exactly what a sparse representation is meant to avoid.
- Constructor: copy nums into a field.
- dotProduct: loop i over 0..n-1 and add values[i] * vec.values[i].
class SparseVector {
private final int[] values;
public SparseVector(int[] nums) {
values = nums.clone();
}
public int dotProduct(SparseVector vec) {
int sum = 0;
for (int i = 0; i < values.length; i++) {
sum += values[i] * vec.values[i];
}
return sum;
}
}class SparseVector:
def __init__(self, nums: List[int]):
self.values = list(nums)
def dotProduct(self, vec: 'SparseVector') -> int:
total = 0
for i in range(len(self.values)):
total += self.values[i] * vec.values[i]
return totalclass SparseVector {
public:
vector<int> values;
SparseVector(vector<int>& nums) : values(nums) {}
int dotProduct(SparseVector& vec) {
int sum = 0;
for (size_t i = 0; i < values.size(); i++) {
sum += values[i] * vec.values[i];
}
return sum;
}
};class SparseVector {
constructor(nums) {
this.values = nums.slice();
}
dotProduct(vec) {
let sum = 0;
for (let i = 0; i < this.values.length; i++) {
sum += this.values[i] * vec.values[i];
}
return sum;
}
}2Hash map of non-zeros
O(n) to build, O(min(k1, k2)) per productBuilding scans the array once; the product only visits the non-zeros of the sparser vector, with O(1) average lookups.O(k)k = number of non-zero entries stored in the map.Keep only the non-zero entries in a map from index to value. For the dot product, walk the smaller map and look each index up in the other map; missing keys mean a zero and are skipped.
- Constructor: for each i with nums[i] != 0, put i -> nums[i] in a map.
- dotProduct: let small be the map with fewer entries and big the other one.
- For each (i, v) in small, if big has i, add v * big.get(i).
class SparseVector {
private final Map<Integer, Integer> nonZero = new HashMap<>();
public SparseVector(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) nonZero.put(i, nums[i]);
}
}
public int dotProduct(SparseVector vec) {
Map<Integer, Integer> small = nonZero, big = vec.nonZero;
if (small.size() > big.size()) {
Map<Integer, Integer> t = small;
small = big;
big = t;
}
int sum = 0;
for (Map.Entry<Integer, Integer> e : small.entrySet()) {
Integer other = big.get(e.getKey());
if (other != null) sum += e.getValue() * other;
}
return sum;
}
}class SparseVector:
def __init__(self, nums: List[int]):
self.non_zero = {i: x for i, x in enumerate(nums) if x != 0}
def dotProduct(self, vec: 'SparseVector') -> int:
small, big = self.non_zero, vec.non_zero
if len(small) > len(big):
small, big = big, small
total = 0
for i, v in small.items():
if i in big:
total += v * big[i]
return totalclass SparseVector {
public:
unordered_map<int, int> nonZero;
SparseVector(vector<int>& nums) {
for (int i = 0; i < (int)nums.size(); i++) {
if (nums[i] != 0) nonZero[i] = nums[i];
}
}
int dotProduct(SparseVector& vec) {
unordered_map<int, int>* small = &nonZero;
unordered_map<int, int>* big = &vec.nonZero;
if (small->size() > big->size()) swap(small, big);
int sum = 0;
for (auto& [i, v] : *small) {
auto it = big->find(i);
if (it != big->end()) sum += v * it->second;
}
return sum;
}
};class SparseVector {
constructor(nums) {
this.nonZero = new Map();
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) this.nonZero.set(i, nums[i]);
}
}
dotProduct(vec) {
let small = this.nonZero, big = vec.nonZero;
if (small.size > big.size) [small, big] = [big, small];
let sum = 0;
for (const [i, v] of small) {
if (big.has(i)) sum += v * big.get(i);
}
return sum;
}
}3Optimal (index-value pairs + two pointers)
O(n) to build, O(k1 + k2) per productEach pointer only moves forward over the stored non-zeros.O(k)Two arrays of length k, the number of non-zero entries.Store the non-zero entries as two parallel arrays, indices in increasing order with their values. Two such sorted index lists can be intersected with a merge-style two-pointer walk: advance whichever pointer has the smaller index, and multiply when they match. No hashing, cache friendly, and it works even when both vectors are large.
- Constructor: count the non-zeros, then fill idx[] and val[] in index order.
- dotProduct: i = 0 over this vector, j = 0 over vec.
- If idx[i] == vec.idx[j], add val[i] * vec.val[j] and advance both.
- Otherwise advance the pointer with the smaller index.
- Stop when either list runs out.
class SparseVector {
private final int[] idx;
private final int[] val;
public SparseVector(int[] nums) {
int k = 0;
for (int x : nums) if (x != 0) k++;
idx = new int[k];
val = new int[k];
int p = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
idx[p] = i;
val[p] = nums[i];
p++;
}
}
}
public int dotProduct(SparseVector vec) {
int i = 0, j = 0, sum = 0;
while (i < idx.length && j < vec.idx.length) {
if (idx[i] == vec.idx[j]) {
sum += val[i] * vec.val[j];
i++;
j++;
} else if (idx[i] < vec.idx[j]) {
i++;
} else {
j++;
}
}
return sum;
}
}class SparseVector:
def __init__(self, nums: List[int]):
self.idx = [i for i, x in enumerate(nums) if x != 0]
self.val = [x for x in nums if x != 0]
def dotProduct(self, vec: 'SparseVector') -> int:
i = j = total = 0
a, b = self.idx, vec.idx
while i < len(a) and j < len(b):
if a[i] == b[j]:
total += self.val[i] * vec.val[j]
i += 1
j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
return totalclass SparseVector {
public:
vector<int> idx, val;
SparseVector(vector<int>& nums) {
for (int i = 0; i < (int)nums.size(); i++) {
if (nums[i] != 0) {
idx.push_back(i);
val.push_back(nums[i]);
}
}
}
int dotProduct(SparseVector& vec) {
size_t i = 0, j = 0;
int sum = 0;
while (i < idx.size() && j < vec.idx.size()) {
if (idx[i] == vec.idx[j]) {
sum += val[i] * vec.val[j];
i++;
j++;
} else if (idx[i] < vec.idx[j]) {
i++;
} else {
j++;
}
}
return sum;
}
};class SparseVector {
constructor(nums) {
this.idx = [];
this.val = [];
for (let i = 0; i < nums.length; i++) {
if (nums[i] !== 0) {
this.idx.push(i);
this.val.push(nums[i]);
}
}
}
dotProduct(vec) {
let i = 0, j = 0, sum = 0;
while (i < this.idx.length && j < vec.idx.length) {
if (this.idx[i] === vec.idx[j]) {
sum += this.val[i] * vec.val[j];
i++;
j++;
} else if (this.idx[i] < vec.idx[j]) {
i++;
} else {
j++;
}
}
return sum;
}
}Edge cases to test
- One vector is all zeros: the answer is 0
- No overlapping non-zero positions
- Both vectors fully dense (no zeros at all)
- Length 1
- One vector has far fewer non-zeros than the other
Hints
Hint 1
A product is non-zero only where BOTH vectors are non-zero. Which positions can you skip entirely?
Hint 2
Store only the non-zero entries when the vector is built. How do you then find positions the two vectors share?
Hint 3
If both vectors keep their non-zero indices in increasing order, a two-pointer walk finds the shared ones without any hashing.
FAQ
What is the best time complexity for Dot Product of Two Sparse Vectors?
Optimal (index-value pairs + two pointers) runs in O(n) to build, O(k1 + k2) per product time and O(k) extra space. Each pointer only moves forward over the stored non-zeros.
Which pattern does Dot Product of Two Sparse Vectors use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Dot Product of Two Sparse Vectors?
Yes. Brute force (dense copy) takes O(n) time and O(n) space. Keep the whole array inside the object and multiply position by position.
Which edge cases should I test for Dot Product of Two Sparse Vectors?
One vector is all zeros: the answer is 0; No overlapping non-zero positions; Both vectors fully dense (no zeros at all); Length 1; One vector has far fewer non-zeros than the other.