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

PYTHON · TWO POINTERS

Dot Product Of Two Sparse Vectors in Python, explained

Problem overview

A sparse vector is mostly zeros. Instead of storing every zero, it is stored as a list of [index, value] pairs for the nonzero entries only, sorted by index. The vector [6, 0, 0, 9, 7] becomes [[0, 6], [3, 9], [4, 7]].

The method dot receives two such lists, first and second, and returns their dot product: multiply the entries at the same position and add up the products. In the example, first is [[0, 6], [3, 9], [4, 7]] and second is [[1, 3], [3, 4]], which stands for [0, 3, 0, 4, 0]. Only position 3 is nonzero in both, so the answer is 9 * 4 = 36.

Approach: walk both lists in step

Expanding both vectors to full length and multiplying would work, but it wastes time and memory on zeros, which is the point of the sparse form. A product contributes only where both vectors are nonzero, that is, where both lists have an entry with the same index.

Because both lists are sorted by index, finding the shared indices is the same job as merging two sorted lists. Keep one pointer in each list and compare the indices they point to:

If the first list's index is smaller, that position is zero in the second vector. It contributes nothing, so move the first pointer forward.
If the second list's index is smaller, move the second pointer forward for the same reason.
If the indices are equal, multiply the two values, add the result to the total, and move both pointers.

Each step moves at least one pointer, and the loop ends when either list is used up. Whatever remains in the other list pairs with zeros.

Step by step

Set the pointers and the total. i = j = result = 0 creates all three at once. i points into first, j into second, and result collects the sum.
Loop while both pointers are in range. The condition i < len(first) and j < len(second) stops as soon as either list is finished, so neither index goes past the end.
First index is smaller: first[i][0] < second[j][0]. The first element of an entry is its index. Advance i.
Second index is smaller: an elif with the comparison reversed advances j.
Indices match: the else branch multiplies the values, which are element 1 of each pair, and adds the product to result.
Advance both pointers in the same branch, because the matched entries are used up. No index repeats within a list, so the matched entries can't pair with anything else.
Return result. Leftover entries pair with zeros and add nothing.

Tracing the example: the pointers start at [0, 6] and [1, 3]. Index 0 is smaller, so i moves. Now it is [3, 9] against [1, 3], and 1 is smaller, so j moves. Then [3, 9] against [3, 4]: the indices match, so the total becomes 36 and both pointers move. The second list is finished, the loop ends, and 36 is returned.

The solution in Python

class Solution:
    def dot(self, first: List[List[int]], second: List[List[int]]) -> int:
        i = j = result = 0
        
        while (i < len(first) and j < len(second)):
            if (first[i][0] < second[j][0]):
                i += 1
            elif (first[i][0] > second[j][0]):
                j += 1
            else:
                result += first[i][1] * second[j][1]
                i += 1
                j += 1

        return result

Python details to know:

Chained assignment. i = j = result = 0 binds all three names to the integer 0. Integers are immutable, so later changes such as i += 1 rebind only i. Chaining mutable objects is different: after a = b = [] both names refer to the same list.
Parentheses are optional. The brackets around the conditions in while and if are allowed but not required in Python.
and short-circuits. If i < len(first) is false, Python doesn't evaluate the second half. The indexing inside the loop is therefore safe.
Big numbers. Python integers don't overflow, so a large product or total is still exact.

Complexity

Time: O(a + b), where a and b are the numbers of stored entries in the two lists. Every pass moves at least one pointer forward, and neither pointer moves back, so there are at most a + b passes. The vectors' full length never matters.

Space: O(1). Three integers are enough.

Edge cases and common mistakes

No shared index. [[0, 6]] and [[5, 1]] give 0.
An empty vector. If either list is empty, the loop never runs and the result is 0.
Negative values. [[2, 5]] and [[2, -3]] give -15. The code needs nothing special.
Everything shared. [[0, 1], [1, 2]] and [[0, 3], [1, 4]] give 11, that is 3 plus 8.
Mixing up index and value. Element 0 of each pair is the index and element 1 is the value. Comparing values to decide which pointer moves would give wrong answers.
Not advancing on a match. If the else branch added to result but moved neither pointer, the same entries would match forever and the loop would never end.
Unsorted input. The method depends on both lists being sorted by index. The lesson's statement lists the entries in that order.

Testing

[[0, 6], [3, 9], [4, 7]] and [[1, 3], [3, 4]] give 36.
[[0, 6]] and [[5, 1]] give 0.
[[2, 5]] and [[2, -3]] give -15.
[[0, 1], [1, 2]] and [[0, 3], [1, 4]] give 11.
[] and [[1, 3]] give 0.

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

Start learning free