Start learning free

LESSON 231 OF 344 · TWO POINTERS

Dot Product of Two Sparse Vectors in Java: 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
    Ctrl + Enter to check

    JAVA · TWO POINTERS

    Dot Product Of Two Sparse Vectors in Java, explained

    Problem overview

    A sparse vector is mostly zeros, so storing every zero is wasteful. The lesson stores only the non-zero entries, as pairs [index, value]. The vector [6, 0, 0, 9, 7] becomes [[0, 6], [3, 9], [4, 7]].

    The method dot receives two such vectors, first and second, as int[][], and returns their dot product: the sum of first[k] * second[k] over every position k of the full vectors.

    With first = [[0, 6], [3, 9], [4, 7]] and second = [[1, 3], [3, 4]] the full vectors are [6, 0, 0, 9, 7] and [0, 3, 0, 4, 0]. Only position 3 is non-zero in both: 9 * 4 = 36. Every other product has a zero factor, so the answer is 36.

    Approach: walk both lists with two pointers

    A product contributes only where both vectors are non-zero, which means only at indices that appear in both lists. So the job is to find the indices the two lists have in common and multiply the values stored there.

    Expanding both vectors to full length would take time and memory proportional to their length, which defeats the purpose of a sparse format. Instead, use the fact that each list is ordered by increasing index. This is how the lesson's data is laid out, and the approach depends on it. Keep a pointer into each list and compare the two current indices:

    • If the index in first is smaller, that position is missing from second, so its value there is 0 and the product is 0. Advance the pointer in first.
    • If the index in second is smaller, do the same on the other side.
    • If the indices are equal, multiply the two values, add the product to the result, and advance both pointers.

    Each step moves at least one pointer forward, so the loop ends after at most as many steps as the two lists have entries combined. It stops as soon as either list runs out, because the remaining entries of the other list would be matched with implicit zeros.

    On the example, the pointers start at [0, 6] and [1, 3]. Index 0 is smaller, so first advances to [3, 9]. Now 3 against 1: second advances to [3, 4]. The indices match, so the result becomes 36 and both pointers advance. second is exhausted, so the loop ends.

    Step by step

    1. Set up the state. The pointers i and j start at 0, one per list. result starts at 0 and collects the products.
    2. Loop while both pointers are in range. The condition compares i with first.length and j with second.length. Once either list is used up, no more matches are possible, and the condition also prevents reading past the end.
    3. Handle a smaller index in first. Element 0 of each pair is its index. When first[i][0] is smaller, increase i.
    4. Handle a smaller index in second. In an else if, when second[j][0] is smaller, increase j.
    5. Handle a match. In the else branch the indices are equal. Multiply the values, which are element 1 of each pair, and add the product to result.
    6. Advance both pointers after a match. Moving only one would compare the same index again on the next round, and in a vector with unique indices it could never match twice.
    7. Return result after the loop. Entries left over in either list pair with implicit zeros.

    The solution in Java

    class Solution {
    public int dot(int[][] first, int[][] second) {
        int i = 0, j = 0;
        int result = 0;
        
        while (i < first.length && j < second.length) {
            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;
    }
}

    The Java details worth a closer look:

    • Two levels of indexing. first is an array of arrays. first[i] is the i-th pair, an int[] of length 2, and first[i][0] and first[i][1] are its index and value. A first dimension of 0 is legal and means a vector with no non-zero entries.
    • Several declarations on one line. int i = 0, j = 0; declares two int variables of the same type, each with its own initial value.
    • Short-circuit &&. In the loop condition, if i < first.length is false, Java doesn't evaluate the second part. Neither array is read out of range because the condition is checked before every iteration.
    • The product is an int product. A product that exceeds about 2.1 billion wraps around silently in Java and gives a wrong number. For example, 100000 * 100000 evaluates to 1410065408. With larger values, switch result to long and write (long) first[i][1] * second[j][1], so the multiplication itself is done in long.

    Complexity

    Let a and b be the numbers of non-zero entries in first and second.

    Time: O(a + b). Every iteration advances at least one pointer, and the pointers can advance at most a + b times in total. This does not depend on the length of the full vectors, which could be millions of positions long.

    Space: O(1). The method uses three integers and builds nothing new.

    Edge cases and common mistakes

    • No overlap. [[0, 1]] against [[1, 1]] returns 0: the pointers pass each other without a match.
    • An empty vector. If either array has no entries, the loop never starts and the method returns 0.
    • Negative values. [[2, 5]] and [[2, -4]] give -20. The result can be negative.
    • Unsorted entries. The method assumes ascending indices. With first = [[3, 9], [0, 6]] and second = [[0, 5], [3, 2]] it returns 18 instead of the correct 48, because the pointers skip entries they should match. If the order isn't guaranteed, sort each list by index first.
    • Advancing only one pointer on a match. The other pointer stays on an index that has been used up, and the following comparison goes wrong.
    • Looping until both lists end. A condition with || reads past the end of the shorter list and throws ArrayIndexOutOfBoundsException.
    • Mixing up index and value. Element 0 of a pair is the index used for the comparison, and element 1 is the value used in the product.

    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 = [[2, -4]] gives -20.
    • first = [[0, 1]], second = [[1, 1]] gives 0.
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free