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 dot product multiplies two vectors position by position and adds the products: A[0] * B[0] + A[1] * B[1] + .... A sparse vector is one that is mostly zeros, so instead of storing every position it stores only the non-zero entries, each as a pair [index, value]. The vector [6, 0, 0, 9, 7] is stored as [[0, 6], [3, 9], [4, 7]].

The method Dot receives two such lists as int[][], named first and second, and returns the dot product as an int. For first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]] the answer is 36. The only position where both vectors are non-zero is index 3, and 9 * 4 = 36.

Approach: walk both lists in index order

A zero multiplied by anything is zero, so only positions that appear in both lists contribute. Expanding both vectors to full length and multiplying would work, but it throws away the point of the sparse format and could use far more memory than the entries need.

Each list is sorted by index, so a two-pointer scan can find the common indices. Keep a pointer i into first and j into second, and compare the index parts of the current entries:

If first's index is smaller, second has no entry at that position, so its value there is 0 and the product is 0. Skip it by advancing i.
If second's index is smaller, advance j for the same reason.
If the indices are equal, both vectors are non-zero here. Multiply the values, add the product to the total, and advance both pointers.

Every comparison advances at least one pointer, so the work is proportional to the number of entries in the two lists, not to the length of the vectors.

On the example: indices 0 and 1 differ, and 0 is smaller, so i moves. Now 3 meets 1, and 1 is smaller, so j moves. Then 3 meets 3, the values 9 and 4 give 36, and both pointers move. The second list is used up, so the loop ends with 36.

Step by step

Declare the pointers and the total. i and j start at 0, and result starts at 0.
Loop while both lists have entries left. Compare each pointer with its own list's Length. Once either list is exhausted, no further common index is possible.
Skip the smaller index in first. The entry's index is element 0 of the pair, so the test is first[i][0] < second[j][0].
Skip the smaller index in second with the mirror case, in an else if.
Handle a match in the else branch. If neither index is smaller, they are equal. The values are element 1 of each pair, so multiply first[i][1] by second[j][1] and add the product to result.
Advance both pointers in that branch, so the matched entries are not used again.
Return result. Entries left in one list have no partner in the other, so they add nothing.

The solution in C#

class Solution {
    public int Dot(int[][] first, int[][] second) {
        int i = 0, j = 0;
        int result = 0;

        while (i < first.Length && j < second.Length) {
            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;
    }
}

C# notes:

int[][] is a jagged array: an array whose elements are themselves arrays. first[i] is the i-th pair, an int[] of length 2, and first[i][0] is that pair's index. It is different from the rectangular int[,], which is indexed as a[i, j].
Jagged arrays are built by hand, for example new int[][] { new int[] {0, 6}, new int[] {3, 9} }, or with the shorter new[] { new[] {0, 6}, new[] {3, 9} } when the element types can be inferred.
+= adds the right side to the variable, so result += x means result = result + x.
Overflow wraps silently. In normal default (unchecked) code, an int product or sum that is too large does not throw. For example, 100000 * 100000 stored in an int gives 1410065408. The lesson's values are small enough that this does not arise.

Complexity

Time: O(n + m), where n and m are the numbers of non-zero entries in the two vectors. Every iteration advances at least one pointer, and neither pointer moves backward.

Space: O(1). The method uses three integers and builds no new arrays.

Edge cases and common mistakes

No common index. For [[2, 5]] and [[3, 5]] the pointers never meet on an equal index, so the result is 0.
An empty entry list. A vector of all zeros is an empty list. The loop condition fails immediately and the method returns 0.
Mixing up index and value. Element 0 of a pair is the position and element 1 is the stored value. Multiplying the indices instead of the values is an easy slip.
Advancing only one pointer on a match. The matched entry would be compared again on the next pass. Indices are unique within a vector, so the next comparison could not match it, but the extra step is wasted work and obscures the intent. Advance both.
Comparing values instead of indices in the if conditions. Only the index part decides which pointer moves.

Testing

first = [[0, 6], [3, 9], [4, 7]], second = [[1, 3], [3, 4]] gives 36.
first = [], second = [[1, 3]] gives 0.
first = [[2, 5]], second = [[3, 5]] 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