Start learning free

LESSON 231 OF 344 · TWO POINTERS

Dot Product of Two Sparse Vectors in JavaScript: 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
    Ctrl + Enter to check

    JAVASCRIPT · TWO POINTERS

    Dot Product Of Two Sparse Vectors in JavaScript, explained

    Problem overview

    A sparse vector is a vector that is mostly zeros. Instead of storing every position, it is stored as a list of [index, value] pairs, one for each non-zero entry, ordered by index. For example, [6, 0, 0, 9, 7] is stored as [[0, 6], [3, 9], [4, 7]].

    The method dot receives two such lists, first and second, and returns their dot product: the sum, over every position, of the two entries at that position multiplied together. With first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]] the full vectors are [6, 0, 0, 9, 7] and [0, 3, 0, 4, 0]. Only position 3 has a non-zero entry in both vectors, so the result is 9 * 4 = 36.

    Approach: walk both lists at once

    The plain method would expand both vectors into full arrays and multiply position by position. For a vector with a million positions and a handful of non-zero entries, that wastes time and memory on zeros. A product contributes to the sum only if both entries are non-zero, which means only positions that appear in both lists matter.

    Both lists are sorted by index, so finding the shared indices is like merging two sorted lists. Keep one pointer in each list and compare the two current indices:

    • If the index in first is smaller, second has no entry there, so the product is zero. Move the pointer in first forward.
    • If the index in second is smaller, do the same on the other side.
    • If the indices are equal, multiply the two values, add the product to the total, and move both pointers.

    Each step moves at least one pointer forward, so the loop ends after at most as many steps as the two lists hold entries in total. The loop can stop as soon as either list runs out: the entries left over in the other list would pair only with implicit zeros.

    Step by step

    1. Start the pointers and the total. Declare i and j, both 0, on one line, and result at 0. The pointers index into first and second.
    2. Loop while both pointers are in range. The condition i < first.length && j < second.length stops the loop when either list is used up, so neither list is read past its end.
    3. First index smaller. Compare first[i][0] with second[j][0]. Element 0 of a pair is the index. When first's index is smaller, advance i.
    4. Second index smaller. In an else if, advance j.
    5. Indices equal. The remaining else branch handles a match. Add first[i][1] * second[j][1] to result, since element 1 of a pair is the value.
    6. Consume the match. Advance both i and j in the same branch. Neither entry can match anything else, because the indices within one list are all different.
    7. Return result after the loop.

    The solution in JavaScript

    class Solution {
    dot(first, second) {
        let i = 0, j = 0;
        let 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;
    }
}

    On the example, i and j start at 0 and the indices are 0 and 1, so i advances. Next the indices are 3 and 1, so j advances. Then both are 3, so the result becomes 9 * 4 = 36 and both pointers move on. The pointer j is now past the end of second, and the loop stops with 36.

    The JavaScript details worth a look:

    • Nested arrays. A pair is a two-element array, so first[i][0] means "the pair at position i, then its element 0".
    • let i = 0, j = 0; declares two variables in one statement. Both are numbers that change, so let is the right keyword.
    • && short-circuits. If i < first.length is false, the second test isn't evaluated.
    • Numbers are floating point. JavaScript numbers are 64-bit floats, so integer products are exact up to 2^53 - 1 (Number.MAX_SAFE_INTEGER). Beyond that, results lose precision. Typical sparse-vector values stay far below it.

    Complexity

    Let a and b be the lengths of the two lists of pairs, that is, the numbers of non-zero entries.

    Time: O(a + b). Every iteration advances at least one pointer, and the pointers can advance at most a + b times in all. The time doesn't depend on how long the full vectors would be.

    Space: O(1). The code needs only i, j and result.

    Edge cases and common mistakes

    • No shared index. If the vectors never overlap, the loop ends with result still 0. For [[0, 1]] and [[2, 5]] the answer is 0.
    • An empty list. If either list is empty, the loop doesn't run and the answer is 0.
    • Negative values. They multiply as usual. [[0, 2], [5, 3]] and [[0, 4], [5, -1]] give 2 * 4 + 3 * (-1) = 5.
    • Using || in the loop condition. The loop would then keep going after one list ended and read undefined[0], which throws a TypeError.
    • Mixing up index and value. Element 0 is the position and element 1 is the number. Multiplying the indices instead of the values gives a plausible but wrong total.
    • Expanding to full arrays. It works, but costs time and memory proportional to the vector length instead of the number of non-zero entries.

    Testing

    • first = [[0, 6], [3, 9], [4, 7]], second = [[1, 3], [3, 4]] gives 36.
    • first = [], second = [[1, 1]] gives 0.
    • first = [[0, 2], [5, 3]], second = [[0, 4], [5, -1]] gives 5.
    • first = [[0, 1]], second = [[2, 5]] gives 0.
    Keep going with JavaScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free