SeniorCodeOccasionalNot answered yet
Add two sparse vectors given as sorted (index, value) pairs
Two sparse vectors are given as lists of (index, value) pairs sorted by index. Return their sum in the same sparse form, sorted, dropping any entry whose summed value is zero.
Requirements:
- O(|l| + |r|) two-pointer merge.
- Use a wide accumulator to avoid overflow when values add.
struct TItem { int Idx; long long Val; };
std::vector<TItem> sumSparse(const std::vector<TItem>& l, const std::vector<TItem>& r) {
// your code here
}Write the implementation.
Two-pointer merge of the sorted lists: at equal indices add the values, otherwise emit the smaller index and advance that pointer. Skip any result whose summed value is zero (it is no longer sparse-nonzero). Linear in the combined length, O(|l|+|r|).
- ✗Forgetting to drop entries whose summed value is zero
- ✗Advancing both pointers when only one index matched
- ✗Accumulating into a narrow type and overflowing when two large values add
- →How does this differ from a sparse-vector dot product, which multiplies instead?
- →Why must the zero-sum result be removed to stay properly sparse?
Contents
Task
Add two sparse (index, value) vectors with a two-pointer merge in O(|l|+|r|).
Solution
std::vector<TItem> sumSparse(const std::vector<TItem>& l, const std::vector<TItem>& r) {
std::vector<TItem> out;
size_t i = 0, j = 0;
while (i < l.size() || j < r.size()) {
if (j >= r.size() || (i < l.size() && l[i].Idx < r[j].Idx)) {
out.push_back(l[i++]);
} else if (i >= l.size() || r[j].Idx < l[i].Idx) {
out.push_back(r[j++]);
} else { // equal indices
long long sum = l[i].Val + r[j].Val;
if (sum != 0) out.push_back({l[i].Idx, sum});
++i; ++j;
}
}
return out;
}Key points
- Two-pointer merge: add at equal indices, otherwise take the smaller one.
- Zero sums are dropped — otherwise the vector stops being sparse.
- The accumulator is wide so it cannot overflow.
Contents
