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

SWIFT · TWO POINTERS

Dot Product Of Two Sparse Vectors in Swift, explained

Problem overview

A dot product multiplies two vectors position by position and adds the products: A[0] * B[0] + A[1] * B[1] + .... A sparse vector is one where most entries are zero, so the lesson stores only the non-zero ones, as [index, value] pairs sorted by index. The vector [6, 0, 0, 9, 7] is stored as [[0, 6], [3, 9], [4, 7]].

The method dot receives two such lists, first and second, as [[Int]], and returns their dot product as an Int. In the example, first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]] stand for [6, 0, 0, 9, 7] and [0, 3, 0, 4, 0]. The only position where both are non-zero is 3, so the result is 9 * 4 = 36.

Approach: walk both lists by index

Expanding both vectors into full arrays would work, but it wastes time and memory on all the zeros. A product is zero whenever either factor is zero, so only positions that appear in both lists can add anything.

Because each list is sorted by index, you can find those shared positions with two pointers, as in merging two sorted arrays. Keep i on the current entry of first and j on the current entry of second, and compare their indices:

If first's index is smaller, that position is zero in second, because second has already moved past anything smaller, so it contributes nothing. Advance i.
If second's index is smaller, advance j for the mirror reason.
If the indices are equal, both vectors are non-zero here. Add the product of the two values and advance both pointers.

When either list runs out, the remaining entries of the other one line up with zeros, so the loop can stop.

On the example, the first entries are index 0 and index 1, so 0 is smaller and i moves on. Next 3 against 1 moves j. Then 3 against 3 match, adding 9 * 4 = 36. After that j is past the end of second, and the loop ends with 36.

Another way is to put one list into a dictionary from index to value and look up each index of the other list. That also works, but it uses extra memory for the dictionary, while the two-pointer scan relies on the sorted order and needs none.

Step by step

Declare the state. i and j start at 0, one for each list, and result starts at 0 to collect the sum.
Loop while both pointers are in range. Comparing each against its own list's count avoids reading past either end.
First index smaller. Compare first[i][0] with second[j][0]. When the first is smaller, advance i.
Second index smaller. In the mirror case, advance j.
Indices equal. The last branch means the indices match. Add first[i][1] * second[j][1], the product of the two stored values, to result.
Consume the match. Advance both pointers. Advancing only one would try to match the same index again.
Return result.

The solution in Swift

class Solution {
    func dot(_ first: [[Int]], _ second: [[Int]]) -> Int {
        var i = 0, j = 0
        var result = 0

        while i < first.count && j < second.count {
            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
    }
}

Swift details worth knowing:

Nested arrays. The type [[Int]] is an array of arrays of integers. first[i] is one pair, and first[i][0] and first[i][1] are its index and its value. The array has no fixed length of 2, so the code relies on the input holding exactly two numbers per pair.
Declaring several variables. var i = 0, j = 0 declares both pointers in one line.
Compound assignment. result += ... and i += 1 replace ++, which Swift doesn't have.
Overflow traps. Int is 64 bits in Swift. If a product or the sum didn't fit, the program would crash instead of wrapping around. Use the wrapping operators such as &* and &+ only if you want wrapping.
Parameters are constants, and this method only reads them, so nothing is copied or changed.

Complexity

Let n and m be the numbers of non-zero entries in first and second. The length of the full vectors doesn't matter.

Time: O(n + m). Every iteration advances at least one pointer, and neither pointer moves back, so the loop runs at most n + m times.

Space: O(1). The method uses three integers.

Edge cases and common mistakes

No shared positions. [[0, 1], [1, 2]] and [[2, 3], [3, 4]] give 0.
An empty list. A vector of all zeros is an empty list. The loop never starts, and the result is 0.
All positions shared. [[0, 2], [1, 3], [2, 4]] and [[0, 5], [1, 6], [2, 7]] give 10 + 18 + 28 = 56.
Advancing only one pointer on a match. The same index would then be compared again, and a product could be added twice.
Comparing values instead of indices. The sort order is by index, so the comparison must use element 0 of each pair, not element 1.
Checking only one bound. If the loop tested only i, reading second[j] after second is used up would crash the program.

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, 2]] and [[2, 3], [3, 4]] give 0.

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

Start learning free