Dot Product of Two Sparse Vectors

Medium Design Data Structures Pre-processing + tradeoffs Original on LeetCode

Dot Product of Two Sparse Vectors is a medium design data structures problem solved with the pre-processing + tradeoffs pattern. The best approach, optimal (index-value pairs + two pointers), runs in O(n) to build, O(k1 + k2) per product time and O(k) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (dense copy) up.

Problem

A sparse vector is one where most entries are zero. Design a class SparseVector that stores such a vector compactly and can compute its dot product with another SparseVector of the same length.

  • SparseVector(int[] nums) builds the vector from the array nums.
  • int dotProduct(SparseVector vec) returns the dot product of this vector and vec: the sum of this[i] * vec[i] over every index i.

Choose a representation that does not waste work on the zero entries. As a follow-up, think about what changes when only one of the two vectors is sparse.

Examples

Example 1

Input
nums1 = [0, 4, 0, 0, 2], nums2 = [3, 5, 0, 1, 0]
Output
20
Why
Only index 1 is non-zero in both vectors: 4 * 5 = 20. Index 4 pairs 2 with 0 and adds nothing.

Example 2

Input
nums1 = [7, 0, 0], nums2 = [0, 0, 9]
Output
0
Why
The non-zero positions never overlap, so every product is 0.

Example 3

Input
nums1 = [0, 2, 0, 3, 0, 0, 1], nums2 = [0, 6, 0, 0, 0, 0, 8]
Output
20
Why
2 * 6 + 1 * 8 = 12 + 8 = 20.

Constraints

  • n == nums1.length == nums2.length
  • 1 <= n <= 10^5
  • 0 <= nums1[i], nums2[i] <= 100
  • The tests run new SparseVector(nums1).dotProduct(new SparseVector(nums2)).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (dense copy)O(n)O(n)
Hash map of non-zerosO(n) to build, O(min(k1, k2)) per productO(k)
Optimal (index-value pairs + two pointers)O(n) to build, O(k1 + k2) per productO(k)

1Brute force (dense copy)

TimeO(n)Every index is visited, even the zero ones.
SpaceO(n)Each vector stores all n values, zeros included.

Keep the whole array inside the object and multiply position by position. Simple, but it pays for every zero, which is exactly what a sparse representation is meant to avoid.

  1. Constructor: copy nums into a field.
  2. dotProduct: loop i over 0..n-1 and add values[i] * vec.values[i].
class SparseVector {
    private final int[] values;

    public SparseVector(int[] nums) {
        values = nums.clone();
    }

    public int dotProduct(SparseVector vec) {
        int sum = 0;
        for (int i = 0; i < values.length; i++) {
            sum += values[i] * vec.values[i];
        }
        return sum;
    }
}

2Hash map of non-zeros

TimeO(n) to build, O(min(k1, k2)) per productBuilding scans the array once; the product only visits the non-zeros of the sparser vector, with O(1) average lookups.
SpaceO(k)k = number of non-zero entries stored in the map.

Keep only the non-zero entries in a map from index to value. For the dot product, walk the smaller map and look each index up in the other map; missing keys mean a zero and are skipped.

  1. Constructor: for each i with nums[i] != 0, put i -> nums[i] in a map.
  2. dotProduct: let small be the map with fewer entries and big the other one.
  3. For each (i, v) in small, if big has i, add v * big.get(i).
class SparseVector {
    private final Map<Integer, Integer> nonZero = new HashMap<>();

    public SparseVector(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) nonZero.put(i, nums[i]);
        }
    }

    public int dotProduct(SparseVector vec) {
        Map<Integer, Integer> small = nonZero, big = vec.nonZero;
        if (small.size() > big.size()) {
            Map<Integer, Integer> t = small;
            small = big;
            big = t;
        }
        int sum = 0;
        for (Map.Entry<Integer, Integer> e : small.entrySet()) {
            Integer other = big.get(e.getKey());
            if (other != null) sum += e.getValue() * other;
        }
        return sum;
    }
}

3Optimal (index-value pairs + two pointers)

TimeO(n) to build, O(k1 + k2) per productEach pointer only moves forward over the stored non-zeros.
SpaceO(k)Two arrays of length k, the number of non-zero entries.

Store the non-zero entries as two parallel arrays, indices in increasing order with their values. Two such sorted index lists can be intersected with a merge-style two-pointer walk: advance whichever pointer has the smaller index, and multiply when they match. No hashing, cache friendly, and it works even when both vectors are large.

  1. Constructor: count the non-zeros, then fill idx[] and val[] in index order.
  2. dotProduct: i = 0 over this vector, j = 0 over vec.
  3. If idx[i] == vec.idx[j], add val[i] * vec.val[j] and advance both.
  4. Otherwise advance the pointer with the smaller index.
  5. Stop when either list runs out.
class SparseVector {
    private final int[] idx;
    private final int[] val;

    public SparseVector(int[] nums) {
        int k = 0;
        for (int x : nums) if (x != 0) k++;
        idx = new int[k];
        val = new int[k];
        int p = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                idx[p] = i;
                val[p] = nums[i];
                p++;
            }
        }
    }

    public int dotProduct(SparseVector vec) {
        int i = 0, j = 0, sum = 0;
        while (i < idx.length && j < vec.idx.length) {
            if (idx[i] == vec.idx[j]) {
                sum += val[i] * vec.val[j];
                i++;
                j++;
            } else if (idx[i] < vec.idx[j]) {
                i++;
            } else {
                j++;
            }
        }
        return sum;
    }
}

Edge cases to test

  • One vector is all zeros: the answer is 0
  • No overlapping non-zero positions
  • Both vectors fully dense (no zeros at all)
  • Length 1
  • One vector has far fewer non-zeros than the other

Hints

Hint 1

A product is non-zero only where BOTH vectors are non-zero. Which positions can you skip entirely?

Hint 2

Store only the non-zero entries when the vector is built. How do you then find positions the two vectors share?

Hint 3

If both vectors keep their non-zero indices in increasing order, a two-pointer walk finds the shared ones without any hashing.

FAQ

What is the best time complexity for Dot Product of Two Sparse Vectors?

Optimal (index-value pairs + two pointers) runs in O(n) to build, O(k1 + k2) per product time and O(k) extra space. Each pointer only moves forward over the stored non-zeros.

Which pattern does Dot Product of Two Sparse Vectors use?

It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.

Is there a brute force solution for Dot Product of Two Sparse Vectors?

Yes. Brute force (dense copy) takes O(n) time and O(n) space. Keep the whole array inside the object and multiply position by position.

Which edge cases should I test for Dot Product of Two Sparse Vectors?

One vector is all zeros: the answer is 0; No overlapping non-zero positions; Both vectors fully dense (no zeros at all); Length 1; One vector has far fewer non-zeros than the other.