Start learning free

LESSON 258 OF 414 · TWO POINTERS

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

    SCALA · TWO POINTERS

    Dot Product Of Two Sparse Vectors in Scala, explained

    Problem overview

    A sparse vector is a vector that is mostly zeros. Instead of storing every zero, the lesson stores only the non-zero entries, as pairs (index, value). In Scala, a vector is an Array[Array[Int]], where each inner array has two elements: the index at position 0 and the value at position 1. The vector [6, 0, 0, 9, 7] is given as [[0, 6], [3, 9], [4, 7]].

    The method dot(first, second) returns the dot product: the sum of the products of the entries at equal indices. Positions where either vector is zero contribute nothing.

    For first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]], the vectors are [6, 0, 0, 9, 7] and [0, 3, 0, 4, 0]. Only index 3 has a non-zero value in both, so the answer is 9 * 4 = 36.

    Approach: walk both entry lists in step

    Rebuilding the full vectors and multiplying them would work, but it spends time and memory on all the zeros, and the point of the sparse form is to avoid that. A better idea works directly on the entry lists.

    The entries of each vector are sorted by index. Keep a pointer i into first and a pointer j into second, and compare the two current indices:

    • If first's index is smaller, that position is zero in second (it has no entry there), so the product is 0. Skip it by moving i.
    • If second's index is smaller, skip it by moving j for the same reason.
    • If the indices are equal, both vectors are non-zero at this position. Multiply the two values, add the product to the result, and move both pointers.

    This is the same pattern as merging two sorted lists. Each step moves at least one pointer forward, so the loop takes at most n + m steps, where n and m are the numbers of non-zero entries.

    On the example: the indices 0 and 1 compare as 0 < 1, so i moves. Then 3 against 1: j moves. Then 3 against 3: the values 9 and 4 give 36, and both pointers move. Now both pointers are past the end of their lists, so the loop ends with 36.

    Why is skipping safe? Because the entries are sorted, a smaller index in one list can't appear later in the other list: the other list's pointer is already at a larger index. So an entry whose index is smaller than the other pointer's index has no partner at all, and its product with the implicit zero is 0.

    Step by step

    1. Declare three vars set to 0: i and j for the positions in the entry lists, and result for the sum.
    2. Loop while both pointers are in bounds: i < first.length && j < second.length. Here length is the number of entries. Once either list is used up, the remaining entries of the other one pair with zeros.
    3. First index smaller: first(i)(0) < second(j)(0). Move i.
    4. Second index smaller: first(i)(0) > second(j)(0). Move j.
    5. Indices equal: add first(i)(1) * second(j)(1) to result. Position 1 of an entry is its value.
    6. Consume the matched pair: advance both i and j. Moving only one would try to match the same index again.
    7. Return result.

    The solution in Scala

    class Solution {
    def dot(first: Array[Array[Int]], second: Array[Array[Int]]): Int = {
        var i = 0
        var j = 0
        var result = 0

        while (i < first.length && j < second.length) {
            if (first(i)(0) < second(j)(0)) {
                i += 1
            } else if (first(i)(0) > second(j)(0)) {
                j += 1
            } else {
                result += first(i)(1) * second(j)(1)
                i += 1
                j += 1
            }
        }

        return result
    }
}

    The Scala details worth knowing:

    • Two sets of parentheses. first(i) is the i-th entry, an Array[Int], and first(i)(0) indexes into that entry. Scala uses parentheses for indexing at every level.
    • Compound assignment. result += x adds to a var. Scala has no ++, so pointers move with i += 1.
    • The result type is Int. It is 32 bits and wraps silently on overflow, so very large values would need Long.
    • return is allowed here. Ending the method with just result would do the same.

    Complexity

    Time: O(n + m), where n and m are the numbers of stored entries of the two vectors, not the lengths of the full vectors. Each iteration advances at least one pointer, and the pointers never move backward.

    Space: O(1). The method needs only the three variables.

    Edge cases and common mistakes

    • An empty vector. If either entry list is empty, the loop never runs and the result is 0.
    • No shared index. [[0, 1]] and [[1, 1]] have no matching index, so the result is 0.
    • Negative values. [[2, 5]] and [[2, -4]] give -20.
    • Several matches. [[0, 1], [1, 1], [2, 1]] and [[0, 2], [1, 3], [2, 4]] give 2 + 3 + 4 = 9.
    • Advancing only one pointer on a match. The next iteration would compare the same index again, and the product would be added twice.
    • Entries that are not sorted by index. The method relies on the order. For [[3, 1], [1, 1]] and [[1, 5], [3, 5]] it returns 5, although the real dot product is 10.
    • Comparing values instead of indices. The deciding comparison is on element 0 of each entry. Element 1 is only used in the product.

    Testing

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