MiddleCodeOccasionalNot answered yet
Dot product of two run-length-encoded vectors
Two integer vectors of equal logical length are given run-length encoded as lists of (value, count) pairs — e.g. [4,4,5] is [(4,2),(5,1)]. Compute their dot product.
Requirements:
- O(|l| + |r|): walk both RLE lists, never expanding them.
- Use a 64-bit accumulator; do not mutate the inputs.
long long dotProduct(const std::vector<std::pair<int,int>>& l,
const std::vector<std::pair<int,int>>& r) {
// your code here
}Write the implementation.
Walk both lists with two pointers, tracking the remaining count of the current run on each side. At each step consume min(remaining) positions, adding value_l * value_r * min to the accumulator, then advance whichever run is exhausted. O(|l|+|r|), no expansion, 64-bit sum.
- ✗Assuming the two RLE run boundaries line up, instead of consuming the min of remaining counts
- ✗Expanding the vectors and losing the O(|l|+|r|) advantage
- ✗Overflowing a 32-bit accumulator when value*count products are large
- →How does this differ from adding two sparse vectors, which merges instead of multiplying?
- →Why is consuming the min of the two remaining counts the key step?
Contents
Task
Compute the dot product of two RLE vectors without expanding them, in O(|l|+|r|).
Solution
long long dotProduct(const std::vector<std::pair<int,int>>& l,
const std::vector<std::pair<int,int>>& r) {
long long sum = 0;
size_t i = 0, j = 0;
int leftRem = l.empty() ? 0 : l[0].second;
int rightRem = r.empty() ? 0 : r[0].second;
while (i < l.size() && j < r.size()) {
int take = std::min(leftRem, rightRem);
sum += static_cast<long long>(l[i].first) * r[j].first * take;
leftRem -= take; rightRem -= take;
if (leftRem == 0 && ++i < l.size()) leftRem = l[i].second;
if (rightRem == 0 && ++j < r.size()) rightRem = r[j].second;
}
return sum;
}Key points
- Take the
minof the two run remainders and advance the exhausted one. - No expansion, hence O(|l|+|r|).
- A 64-bit accumulator guards against overflow.
Contents
