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

KOTLIN · TWO POINTERS

Dot Product Of Two Sparse Vectors in Kotlin, explained

Problem overview

A dot product multiplies two vectors position by position and adds the results: A[0] * B[0] + A[1] * B[1] + .... A sparse vector is one that is mostly zeros, so it is stored as a list of (index, value) pairs for its nonzero entries only, with indices in increasing order. The vector [6, 0, 0, 9, 7] is stored as [[0, 6], [3, 9], [4, 7]].

The function dot takes two such lists as Array<IntArray>, first and second, and returns their dot product as an Int. With first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]] the result is 36. The vectors are [6, 0, 0, 9, 7] and [0, 3, 0, 4, 0], and the only position where both are nonzero is 3, which contributes 9 * 4 = 36.

Approach: walk both lists in index order

Expanding both vectors to full length and multiplying works, but wastes time and memory when the vectors are huge and nearly empty. A product is nonzero only at positions where both vectors have a stored entry, so only the stored entries matter.

Because each list is sorted by index, you can scan both with one pointer each, like the merge step of merge sort. Compare the indices at the two pointers:

If the first list's index is smaller, that position is zero in the second vector, so its product is zero. Skip it by advancing i.
If the second list's index is smaller, advance j for the same reason.
If the indices are equal, both vectors have a nonzero value there. Add the product of the values and advance both pointers.

Every iteration advances at least one pointer, so the work is proportional to the number of stored entries, not to the vector length.

On the example: indices 0 and 1 compare, 0 is smaller, so i moves. Then 3 and 1, so j moves. Then 3 and 3 match: add 9 * 4 = 36 and move both. Now j is past the end of second, the loop stops, and 36 is returned.

Step by step

Create the state. i and j are the two pointers, and result accumulates the sum. All three are vars starting at 0.
Loop while both pointers are in range. The condition compares i with first.size and j with second.size. When either list is used up, every remaining entry in the other list pairs with a zero.
First index smaller. Compare first[i][0] and second[j][0]. If the first is smaller, do i++.
Second index smaller. In the mirror case, do j++.
Indices equal. In the final else, multiply the values first[i][1] and second[j][1] and add the product to result.
Advance both pointers inside that branch. Moving only one would match the same index again.
Return result after the loop.

The solution in Kotlin

class Solution {
    fun dot(first: Array<IntArray>, second: Array<IntArray>): Int {
        var i = 0
        var j = 0
        var result = 0

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

Kotlin details worth knowing:

Array<IntArray>. This is an array whose elements are IntArrays. Each pair is its own two-element IntArray, so first[i][0] is the index of entry i and first[i][1] is its value. Don't confuse it with Array<Int>, an array of boxed integers, or with List<List<Int>>.
+= on an Int variable. result += x means result = result + x. It works because result is a var.
if/else if/else as a statement. Exactly one branch runs per iteration, and the last else only runs when neither comparison was true, which means the indices are equal.
Overflow. Int is 32 bits and wraps silently. A product like 100000 * 100000 doesn't fit: the dot product of [[0, 100000], [1, 3]] and [[0, 100000], [1, -2]] comes out as 1410065402 here, not 9999999994. Large values would call for Long.

Complexity

Let n and m be the number of stored entries in each list.

Time: O(n + m). Each iteration advances at least one pointer, and neither pointer goes back, so the loop runs at most n + m times. The cost doesn't depend on the full length of the vectors.

Space: O(1). Only three integers are kept. The vectors are not expanded or copied.

Edge cases and common mistakes

No shared index. [[0, 6]] and [[1, 3]] give 0.
An empty list. A vector with no nonzero entries is an empty array, and the loop never runs, so the answer is 0.
Advancing only one pointer on a match. The next iteration would compare the same index again and add a wrong product, or compare against a mismatched index.
Reading the value instead of the index to compare. The comparison uses element 0 of each pair, the position. Element 1 is the value.
Unsorted lists. The scan relies on increasing indices. If the entries weren't in order, matching positions could be skipped.
Negative values. They multiply like any other; the sum can be negative or cancel to 0.

Testing

first = [[0, 6], [3, 9], [4, 7]], second = [[1, 3], [3, 4]] gives 36.
first = [], second = [[1, 3]] gives 0.
first = [[0, 6]], second = [[1, 3]] gives 0.

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

Start learning free