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

RUST · TWO POINTERS

Dot Product Of Two Sparse Vectors in Rust, explained

Problem overview

A sparse vector is mostly zeros, so storing every zero wastes space. Here a sparse vector is a list of (index, value) pairs, one for each non-zero entry, sorted by index. In Rust the function receives them as Vec<Vec<i32>>, where each inner vector holds two numbers: element 0 is the position and element 1 is the value. The dot product of two vectors is the sum of the products of their entries at the same position.

For first = [[0, 6], [3, 9], [4, 7]] (the vector [6, 0, 0, 9, 7]) and second = [[1, 3], [3, 4]] (the vector [0, 3, 0, 4, 0]), the only position where both are non-zero is 3, and the answer is 9 * 4 = 36.

Approach: walk both lists in step

A product is zero unless both entries are non-zero. So only positions that appear in both lists matter, and the zeros that were never stored can be ignored. Expanding both vectors to full length and multiplying would work, but it spends time and memory on exactly the zeros that sparse storage avoids.

Because each list is sorted by position, two pointers can find the shared positions in one pass. Keep i in first and j in second, and compare the two current positions:

If the position in first is smaller, second has an implicit zero there. That entry contributes nothing, so advance i.
If the position in second is smaller, advance j for the same reason.
If the positions are equal, multiply the two values, add the product to the total, and advance both pointers.

The loop ends when either list is used up. Whatever remains in the other list pairs with implicit zeros, so it adds nothing.

On the example, the first positions are 0 against 1. Position 0 is smaller, so i moves on. Then 3 against 1: j moves on. Then 3 against 3: the values 9 and 4 give 36, and both pointers advance. Now second is finished, and the total is 36.

Step by step

Declare the pointers and the total. let (mut i, mut j) = (0usize, 0usize); declares both indices at once, as usize because a Vec is indexed with usize. Then let mut result = 0i32; matches the function's i32 return type.
Loop while i < first.len() && j < second.len(), so neither list is read past its end.
First position smaller. If first[i][0] < second[j][0], do i += 1.
Second position smaller. In an else if, when first[i][0] > second[j][0], do j += 1.
Positions equal. In the final else, add first[i][1] * second[j][1] to result. Matching positions are the only places where both vectors can be non-zero.
Consume the match by advancing both, i += 1 and j += 1. Moving just one would match the same position again.
Return result as the final expression, with no semicolon.

The solution in Rust

impl Solution {
    fn dot(first: Vec<Vec<i32>>, second: Vec<Vec<i32>>) -> i32 {
        let (mut i, mut j) = (0usize, 0usize);
        let mut result = 0i32;

        while i < first.len() && j < second.len() {
            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;
            }
        }

        result
    }
}

Rust details worth knowing:

Two levels of indexing. first[i] is an inner Vec<i32>, and first[i][0] is its first number. Each index is checked at run time, and an out-of-range one panics.
Reads are copies. first[i][1] is an i32, which is Copy, so using it in an expression doesn't move anything out of the vector.
The three-way comparison. The if, else if and else cover less than, greater than and equal. Writing the last case as a plain else is safe because the first two conditions already excluded everything else.
Integer width. The products and the total are i32. In an optimized build an overflow wraps silently, and in a debug build it panics. For example, 100000 * 100000 doesn't fit in an i32 and wraps to 1410065408.
Tuple patterns. let (mut i, mut j) = (...) gives each variable its own mut.

Complexity

Time: O(n + m), where n and m are the numbers of stored non-zero entries in the two vectors, not the full lengths. Each iteration advances at least one pointer, so there are at most n + m iterations.

Space: O(1). Only two indices and the total are kept. The inputs are used as they are.

Edge cases and common mistakes

An empty list. A vector with no non-zero entries has no pairs, so the loop doesn't run and the answer is 0.
No shared position. [[0, 1]] and [[1, 1]] give 0.
Negative values. [[2, 5]] and [[2, -4]] give -20. The sign comes from the multiplication.
Advancing only one pointer on a match. The next iteration would compare the same position again, and the same pair could be counted a second time.
Unsorted entries. The method relies on each list being sorted by position. With [[3, 9], [0, 6]] and [[0, 2], [3, 1]] it returns 9 instead of 21, because the pointers skip past matches.
Mixing up the fields. Element 0 is the position and element 1 is the value. Multiplying the positions by accident compiles fine and gives wrong answers.

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]] and [[1, 1]] give 0.

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

Start learning free