Start learning free

LESSON 235 OF 348 · TWO POINTERS

Dot Product of Two Sparse Vectors in TypeScript: 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

    TYPESCRIPT · TWO POINTERS

    Dot Product Of Two Sparse Vectors in TypeScript, explained

    Problem overview

    The method dot receives two sparse vectors and returns their dot product. The dot product of two vectors of the same length is the sum of the products of the entries at each position: A[0] * B[0] + A[1] * B[1] + ....

    A sparse vector is mostly zeros, so it isn't stored as a full array. It is a list of [index, value] pairs, one for each non-zero entry, in increasing order of index. The vector [6, 0, 0, 9, 7] is stored as [[0, 6], [3, 9], [4, 7]]. In TypeScript, each argument has the type number[][], an array of two-element arrays.

    In the example, first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]]. The first vector is [6, 0, 0, 9, 7] and the second is [0, 3, 0, 4, 0]. The only position where both are non-zero is index 3, and 9 * 4 = 36, which is the answer.

    Approach: walk both lists together

    Expanding both vectors into full arrays and multiplying would work, but it throws away the point of the sparse form: the length could be huge while only a few entries matter. A product is non-zero only at positions where both vectors have a stored entry, so only the stored indices need to be compared.

    Because each list is sorted by index, this is a merge-style walk with two pointers, i for the first list and j for the second. Compare the current indices:

    • If the first index is smaller, that position is zero in the other vector, so the product is 0. Advance i.
    • If the second index is smaller, advance j for the same reason.
    • If the indices are equal, both vectors have a value there. Multiply the values, add the product to the result, and advance both pointers.

    Each iteration advances at least one pointer, so the loop runs at most as many times as the two lists have entries in total.

    On the example:

    1. Indices 0 and 1: 0 is smaller, so i advances.
    2. Indices 3 and 1: 1 is smaller, so j advances.
    3. Indices 3 and 3: equal, so add 9 * 4 = 36, and both advance. Now j is past the end of second.

    The loop stops, and the result is 36.

    Step by step

    1. Declare the pointers and the result. i and j go on one line, and result below them, all starting at 0.
    2. Loop while both pointers are in range. Compare each against its own list's length. Once one list is used up, the other list's remaining entries pair with zeros.
    3. First index smaller. If first[i][0] < second[j][0], do i++.
    4. Second index smaller. Else if first[i][0] > second[j][0], do j++.
    5. Indices match. In the final else, add first[i][1] * second[j][1] to result. Element 0 of a pair is the position and element 1 is the value.
    6. Consume the match. Still in that else block, advance both i and j. Advancing only one would match the same index again.
    7. Return result after the loop.

    The solution in TypeScript

    class Solution {
    dot(first: number[][], second: number[][]): number {
        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;
    }
}

    The TypeScript details worth a closer look:

    • Two-level indexing. The type number[][] means first[i] is a number[] (one pair), and first[i][0] is a number. The compiler doesn't know that each inner array has exactly two elements. A tuple type such as [number, number][] would say so, but the lesson uses number[][].
    • Compound assignment. result += x is shorthand for result = result + x.
    • Numbers are doubles. There is no integer overflow, but integer results lose precision beyond 2^53 (about 9 quadrillion), so a dot product that large would not be exact.
    • Sorted input is assumed. The method never sorts anything. If a list were not in increasing index order, the pointer walk could skip matches.

    Complexity

    Let n and m be the numbers of stored entries in the two vectors.

    Time: O(n + m). Every iteration advances at least one pointer, and a pointer never moves backward, so the loop runs at most n + m times. The cost doesn't depend on the full length of the vectors.

    Space: O(1). The method keeps two pointers and a running sum.

    Edge cases and common mistakes

    • An empty list. A vector with no non-zero entries makes the loop condition false immediately, and the result is 0.
    • No shared index. [[0, 1]] and [[1, 1]] never match, so the result is 0.
    • Negative values. Products can be negative: [[2, 5]] and [[2, -4]] give -20.
    • Advancing only one pointer on a match. The same index would be compared again, with the pointer that didn't move, and the pair would be counted twice.
    • Treating a pair's elements the wrong way round. Index 0 of a pair is the position and index 1 is the value. Multiplying positions instead of values gives wrong sums.
    • Looping until both lists end. After one list ends, nothing is left to multiply, so reading further would only produce undefined.

    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 = [[2, -4]] gives -20.
    • first = [[0, 1]], second = [[1, 1]] gives 0.
    Keep going with TypeScriptAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free