Dot Product of Two Sparse Vectors in C++: Two Pointers

Practice O(n) Read the full explanation

Given two sparse vectors, compute their dot product.

A sparse vector is a vector that has mostly zero values.

Dot product of two vectors is the sum of their individual products.

For example, if we have vectors A and B of equal length n, their dot product is:

A * B = A[0] * B[0] + A[1] * B[1] + ... + A[n - 1] * B[n - 1]

We represent a sparse vector as a list of pairs (index, value), where value != 0.

E.g. the vector [6, 0, 0, 9, 7] will be given as [[0, 6], [3, 9], [4, 7]]

Example:

Input: first = [[0, 6], [3, 9], [4, 7]]
       second = [[1, 3], [3, 4]]

Output: 36

Explanation:
[6, 0, 0, 9, 7] * [0, 3, 0, 4, 0] = 
= 6 * 0 + 0 * 3 + 0 * 0 + 9 * 4 + 7 * 0 = 36

STEP 1 OF 7

Guided

Ctrl + Enter to check

C++ · TWO POINTERS

Dot Product Of Two Sparse Vectors in C++, explained

Problem overview

A sparse vector is a vector that is mostly zeros. Instead of storing every zero, it is stored as a list of (index, value) pairs for the nonzero entries only. For example, [6, 0, 0, 9, 7] is stored as [[0, 6], [3, 9], [4, 7]].

The function dot receives two such lists, first and second, and returns their dot product: the sum of A[k] * B[k] over all positions k. In the example, first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]]. As full vectors they are [6, 0, 0, 9, 7] and [0, 3, 0, 4, 0]. Only position 3 has a nonzero value in both, so the answer is 9 * 4 = 36.

Approach: walk both lists together

A product is zero when either factor is zero. So only positions where both vectors have a stored entry can add anything to the sum. The task is to find those shared indices.

Each list is sorted by index, with the entries in increasing index order. That allows the same merge-style walk used for combining sorted lists, with one pointer in each list:

If the current index in first is smaller, second has no entry at that index, so the product is 0. Skip the entry in first.
If the current index in second is smaller, skip the entry in second for the same reason.
If the indices are equal, multiply the two values, add the product to the result and move both pointers.

Each step moves at least one pointer forward, so the walk ends after at most a + b steps, where a and b are the list lengths. It never touches the zeros, so the cost depends on the number of stored entries, not on the full length of the vectors. A full-length vector with a million positions but ten stored entries takes about ten steps.

The walk can stop as soon as either pointer runs out. Any entries left in the other list have no counterpart, so they would multiply with zero.

Step by step

Declare the state. The pointers i and j start at 0, and result starts at 0.
Loop while both lists have entries left. Compare i with first.size() and j with second.size(), joined with &&. This keeps both reads inside the vectors.
First index smaller. Each pair is stored as [index, value], so first[i][0] is the index. If it is smaller than second[j][0], advance i.
Second index smaller. In the mirror case, advance j.
Indices equal. In the else branch, add first[i][1] * second[j][1] to result. The value is element 1 of each pair.
Consume the match. Advance both pointers. Moving only one would compare the same index again.
Return result once the loop ends.

The solution in C++

class Solution {
public:
    int dot(vector<vector<int>>& first, vector<vector<int>>& second) {
        int i = 0, j = 0;
        int result = 0;
        
        while (i < first.size() && j < second.size()) {
            if (first[i][0] < second[j][0]) {
                i++;
            } else if (first[i][0] > second[j][0]) {
                j++;
            } else {
                result += first[i][1] * second[j][1];
                i++;
                j++;
            }
        }
        
        return result;
    }
};

Tracing the example: at i = 0, j = 0 the indices are 0 and 1, so i advances. Now 3 is compared with 1, so j advances. Now 3 equals 3, so result becomes 36 and both pointers move. The second list is exhausted, the loop ends, and 36 is returned. The entry [4, 7] is never examined, which is correct.

The C++ details worth knowing:

Vector of vectors. Each pair is a small vector<int> of two numbers, so first[i][0] reads the index and first[i][1] the value. No bounds check is made by [], which is why the loop condition has to keep i and j in range.
Two declarations on one line. int i = 0, j = 0; declares two separate int variables, each with its own initial value.
Signed against unsigned. i < first.size() compares an int with an unsigned type. For a non-negative i that is correct, though a compiler may warn.
Short-circuit evaluation. The && operator evaluates its right side only if the left side is true. Here both sides are bounds checks, so the order doesn't hide a problem.
Overflow. The products and the sum are int. If the values are large enough that the true result exceeds the int range, signed overflow is undefined behaviour in C++. For large values, accumulate in long long and cast the factors to long long before multiplying.

Complexity

Time: O(a + b). Every iteration advances at least one pointer, and each pointer moves at most to the end of its list.

Space: O(1). The function uses three integers. The lists are taken by reference and are not copied.

A dense approach, which expands both vectors to full length and multiplies position by position, costs time and memory proportional to the vector length. For sparse data that is far more than the number of stored entries.

Edge cases and common mistakes

An empty list. If either vector has no nonzero entries, the loop never runs and the result is 0.
No shared index. [[2, 1]] and [[3, 1]] give 0.
Negative values. [[0, 2], [4, 5]] with [[0, 3], [2, 1], [4, -2]] gives 6 - 10 = -4.
Advancing only one pointer on a match. The next iteration would compare the same index again and add the product a second time.
Using || instead of &&. Once one list is exhausted, the loop would read past its end.
Multiplying the indices. The index is element 0 and the value is element 1. Mixing them up gives a result that looks plausible but is wrong.
Assuming the lists are sorted. The walk depends on ascending indices. If the input could be unsorted, sort each list by index first.

Testing

first = [[0, 6], [3, 9], [4, 7]], second = [[1, 3], [3, 4]] gives 36.
first = [[0, 6], [3, 9], [4, 7]], second = [] gives 0.
first = [[0, 2], [4, 5]], second = [[0, 3], [2, 1], [4, -2]] gives -4.
first = [[2, 1]], second = [[3, 1]] gives 0.

Keep going with C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free