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

Guided

Ctrl + Enter to check

GO · TWO POINTERS

Dot Product Of Two Sparse Vectors in Go, explained

Problem overview

The function dot receives two sparse vectors, first and second, and returns their dot product: the sum of A[k] * B[k] over every position k. A sparse vector is mostly zeros, so it is stored as a list of [index, value] pairs, one per nonzero position, in increasing order of index. In Go that is a [][]int: each inner slice has the index at position 0 and the value at position 1.

In the example, first = [[0, 6], [3, 9], [4, 7]] stands for [6, 0, 0, 9, 7] and second = [[1, 3], [3, 4]] stands for [0, 3, 0, 4, 0]. Only position 3 is nonzero in both vectors, so the dot product is 9 * 4 = 36.

Approach: walk both lists at once

The obvious route rebuilds both full vectors and multiplies them position by position. That works, but its cost depends on the vectors' length rather than on how many nonzero entries they have, and the whole point of a sparse format is to avoid touching the zeros.

A product contributes to the sum only when both vectors are nonzero at the same position. Because each list is sorted by index, finding those shared positions is the same job as merging two sorted lists. Keep one pointer in each list and compare the indices they point at:

If the index in first is smaller, second has an implicit 0 there. That product is 0, so skip the entry in first.
If the 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 total, and move past both entries.

Every step moves at least one pointer forward, and each pointer only moves forward, so the loop ends after at most len(first) + len(second) steps.

Tracing the example: the pointers start at [0, 6] and [1, 3]. Index 0 is smaller, so the first pointer moves to [3, 9]. Now 3 is larger than 1, so the second pointer moves to [3, 4]. The indices match: 9 * 4 = 36 goes into the total and both pointers advance. The second list is used up, so the loop stops. The entry [4, 7] is never needed, because second has nothing at or beyond index 4.

Step by step

Declare the pointers and the total on one line: i and j are positions in the two lists, and result collects the sum. All three start at 0.
Loop while both pointers are in range. Go's only loop keyword is for, and for cond { ... } plays the role of while. Once either list runs out, no further pair of indices can match, so stopping there is correct.
Handle the case where first is behind by advancing i.
Handle the mirror case with an else if that advances j.
Handle equal indices in the final else: add the product of the two stored values and advance both pointers. Advancing only one would compare the same index again and count it twice.
Return result after the loop. Whatever is left in the longer list pairs with implicit zeros.

The solution in Go

func dot(first, second [][]int) int {
    i, j, result := 0, 0, 0
    for i < len(first) && j < len(second) {
        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
}

A few Go details:

Multiple assignment with :=. i, j, result := 0, 0, 0 declares three int variables in one statement. Go reports an unused local variable as a compile error, and all three are used.
A loop condition without parentheses. Go does not wrap the condition of for or if in parentheses, but the braces are mandatory. The else if and else keywords must sit on the same line as the closing brace before them.
first[i][0] versus first[i][1]. first[i] is a slice holding one pair, so the extra subscript picks the index (0) or the value (1).
++ is a statement. In Go, i++ cannot be used inside an expression such as a[i++], so each advance gets its own line.

Complexity

Time: O(n + m), where n and m are the numbers of nonzero entries in the two vectors. Each iteration advances at least one pointer, and the pointers never move back.

Space: O(1). The function keeps three integers and does not copy the lists.

Edge cases and common mistakes

An empty list. If either vector has no nonzero entries, the loop body never runs and the function returns 0. This includes nil slices, because len(nil) is 0.
No shared position. [[2, 5]] and [[3, 5]] never match, so the result is 0, even though both vectors are nonzero.
Negative values. Products can be negative: [[0, 2], [5, -3]] with [[0, 4], [5, 2], [9, 1]] gives 8 + (-6) = 2.
Forgetting to advance both pointers on a match. The loop then compares the same two entries forever and never ends.
Comparing values instead of indices. The comparisons use element 0 of each pair. Element 1 is only for the product.
Integer overflow. int is 64 bits, and a product or sum beyond that wraps around silently instead of raising an error. Ordinary inputs stay far from that limit.

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

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

Start learning free