Dot Product of Two Sparse Vectors

Dot Product of Two Sparse Vectors is a design problem hiding inside a math problem. The math is easy. The real test is how you store a vector that is mostly zeros. Store it the wrong way and you waste huge amounts of memory and time. Store it the smart way and the interviewer smiles.

🎯 The Problem

You take the dot product of two vectors, where almost every value is zero.

What the math is:

• A vector here is a list of numbers.
• The dot product multiplies matching positions and adds the products.
• So position 0 times position 0, plus position 1 times position 1, and so on.

What sparse means:

• A sparse vector has almost every value zero. Only a few positions hold a real number.
• Imagine a million slots where only ten are non-zero.
• Storing all million is a waste, because anything times zero is zero.
• Only positions that are non-zero in both vectors add anything.

Input:  v1 = [1, 0, 0, 2, 3]
        v2 = [0, 3, 0, 4, 0]
Output: 8

Explanation:
- Multiply matching positions: 1*0 + 0*3 + 0*0 + 2*4 + 3*0
- That is 0 + 0 + 0 + 8 + 0 = 8
- Only position 3 has a non-zero value in BOTH vectors, so only it matters.

Here are the two vectors with their zeros shown faded. Only position 3 lines up with a non-zero in both. This first diagram shows why most of the work is wasted on zeros.

So only the positions where both vectors are non-zero add anything. Everything else multiplies to zero. The smart storage drops the zeros entirely.

🐢 Approach 1: Full Scan Over Both Vectors (Brute Force)

The idea in one line: keep both vectors whole and multiply every matching position.

The idea:

• Store both vectors as full lists.
• Walk every position from start to end.
• Multiply v1[i] by v2[i] and add it to a total.

Why it is weak:

• A million-slot vector with ten non-zero values still does a million multiplications.
• Almost every product is zero times something, which adds nothing.
• You burn time and memory on positions that never mattered.

Here is the full-scan code:

class SparseVector:
    def __init__(self, nums):
        self.nums = nums

    def dotProduct(self, vec):
        total = 0
        for i in range(len(self.nums)):
            total += self.nums[i] * vec.nums[i]
        return total

⚡ Approach 2: Non-Zero Pairs With Two Pointers (Best)

The idea in one line: store only the non-zero values as index pairs, then walk the two lists together.

The idea:

• Do not store the full vector. Store only positions with a real value.
• For each non-zero value, keep a pair: its index and its value. This is a list of index value pairs.
• So [1, 0, 0, 2, 3] becomes [(0,1), (3,2), (4,3)]. The zeros are gone.

How it works:

• Use the two-pointer technique. Keep one marker on each list.
• If both pointers show the same index, both vectors have a value there. Multiply, add to the total, move both.
• If one index is smaller, that position is zero in the other vector. Move only the pointer that is behind.
• Stop when either list runs out.

Why it is fast:

• A vector of a million slots and ten non-zero values now takes ten pairs, not a million.
• The walk visits each stored pair once.
• No multiplication is wasted on a zero.

Here is the two-pointer non-zero-pairs code:

class SparseVector:
    def __init__(self, nums):
        self.pairs = [(i, num) for i, num in enumerate(nums) if num != 0]

    def dotProduct(self, vec):
        i = j = total = 0
        while i < len(self.pairs) and j < len(vec.pairs):
            a_index, a_value = self.pairs[i]
            b_index, b_value = vec.pairs[j]
            if a_index == b_index:
                total += a_value * b_value
                i += 1
                j += 1
            elif a_index < b_index:
                i += 1
            else:
                j += 1
        return total

🗂️ Approach 3: Hash Map of Non-Zero Values (Alternative)

The idea in one line: store one vector’s non-zero values in a map, then look up each index of the other.

The idea:

• Store the non-zero values of one vector as a hash map from index to value.
• A hash map gives a direct lookup by index.

How it works:

• Walk the non-zero pairs of the shorter vector.
• For each index, check if the map holds it.
• If it does, multiply the two values and add to the total.

Why it is handy:

• It does not need either list to be sorted.
• It shines when one vector is sparse and the other is dense.
• The lookup is a direct hash hit, not a walk.

Why it is weaker than two pointers:

• A hash map costs extra memory for the buckets.
• A hash lookup is slower in practice than stepping a pointer.

This second diagram shows the two-pointer walk over the stored pairs. Only the matching index 3 adds to the answer.

Steps to Solve

1. Build each vector as a list of (index, value) pairs, keeping only non-zero values, in index order.
2. Put one pointer at the start of each pair list. Start a total at zero.
3. Compare the index at the two pointers.
4. If the indices are equal, multiply the two values, add to the total, and move both pointers forward.
5. If one index is smaller, move only that pointer forward, because the other vector has a zero there.
6. Stop when either pointer reaches the end of its list.
7. The total is the dot product.

#include <stdio.h>

typedef struct { int index; int value; } Pair;

// keep only non-zero entries, return how many pairs were made
int buildPairs(int *vec, int n, Pair *out) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (vec[i] != 0) {
            out[count].index = i;
            out[count].value = vec[i];
            count++;
        }
    }
    return count;
}

int dotProduct(Pair *a, int aLen, Pair *b, int bLen) {
    int total = 0, i = 0, j = 0;
    while (i < aLen && j < bLen) {
        if (a[i].index == b[j].index) {       // both non-zero here
            total += a[i].value * b[j].value;
            i++; j++;
        } else if (a[i].index < b[j].index) {
            i++;                              // a is behind, move it
        } else {
            j++;                              // b is behind, move it
        }
    }
    return total;
}

int main(void) {
    int v1[] = {1, 0, 0, 2, 3};
    int v2[] = {0, 3, 0, 4, 0};
    Pair p1[5], p2[5];
    int len1 = buildPairs(v1, 5, p1);
    int len2 = buildPairs(v2, 5, p2);
    printf("%d\n", dotProduct(p1, len1, p2, len2));
    return 0;
}

8

#include <iostream>
#include <vector>
using namespace std;

class SparseVector {
public:
    vector<pair<int,int>> pairs;   // (index, value) for non-zero entries
    SparseVector(vector<int>& nums) {
        for (int i = 0; i < (int)nums.size(); i++) {
            if (nums[i] != 0) pairs.push_back({i, nums[i]});
        }
    }

    int dot(SparseVector& other) {
        int total = 0, i = 0, j = 0;
        while (i < (int)pairs.size() && j < (int)other.pairs.size()) {
            if (pairs[i].first == other.pairs[j].first) {   // same index
                total += pairs[i].second * other.pairs[j].second;
                i++; j++;
            } else if (pairs[i].first < other.pairs[j].first) {
                i++;
            } else {
                j++;
            }
        }
        return total;
    }
};

int main() {
    vector<int> v1 = {1, 0, 0, 2, 3};
    vector<int> v2 = {0, 3, 0, 4, 0};
    SparseVector a(v1), b(v2);
    cout << a.dot(b) << endl;
    return 0;
}

8

import java.util.ArrayList;
import java.util.List;

public class SparseVector {
    private List<int[]> pairs = new ArrayList<>(); // each int[] is {index, value}

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

    public int dot(SparseVector other) {
        int total = 0, i = 0, j = 0;
        while (i < pairs.size() && j < other.pairs.size()) {
            int[] a = pairs.get(i);
            int[] b = other.pairs.get(j);
            if (a[0] == b[0]) {              // same index
                total += a[1] * b[1];
                i++; j++;
            } else if (a[0] < b[0]) {
                i++;
            } else {
                j++;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        SparseVector a = new SparseVector(new int[]{1, 0, 0, 2, 3});
        SparseVector b = new SparseVector(new int[]{0, 3, 0, 4, 0});
        System.out.println(a.dot(b));
    }
}

8

class SparseVector:
    def __init__(self, nums):
        # keep only non-zero entries as (index, value) pairs
        self.pairs = [(i, v) for i, v in enumerate(nums) if v != 0]

    def dot(self, other):
        total = 0
        i, j = 0, 0                          # one pointer per vector
        while i < len(self.pairs) and j < len(other.pairs):
            idx_a, val_a = self.pairs[i]
            idx_b, val_b = other.pairs[j]
            if idx_a == idx_b:               # both vectors non-zero here
                total += val_a * val_b
                i += 1
                j += 1
            elif idx_a < idx_b:              # a is behind, advance a
                i += 1
            else:                            # b is behind, advance b
                j += 1
        return total


v1 = SparseVector([1, 0, 0, 2, 3])
v2 = SparseVector([0, 3, 0, 4, 0])
print(v1.dot(v2))

8

class SparseVector {
  constructor(nums) {
    this.pairs = []; // [index, value] for non-zero entries
    for (let i = 0; i < nums.length; i++) {
      if (nums[i] !== 0) this.pairs.push([i, nums[i]]);
    }
  }

  dot(other) {
    let total = 0;
    let i = 0;
    let j = 0;
    while (i < this.pairs.length && j < other.pairs.length) {
      const [idxA, valA] = this.pairs[i];
      const [idxB, valB] = other.pairs[j];
      if (idxA === idxB) {        // both non-zero here
        total += valA * valB;
        i++;
        j++;
      } else if (idxA < idxB) {   // a is behind, advance a
        i++;
      } else {                    // b is behind, advance b
        j++;
      }
    }
    return total;
  }
}

const v1 = new SparseVector([1, 0, 0, 2, 3]);
const v2 = new SparseVector([0, 3, 0, 4, 0]);
console.log(v1.dot(v2));

8

Let us read the Python version line by line, because the storage choice and the two-pointer walk are what the interview is about.

self.pairs = [(i, v) for i, v in enumerate(nums) if v != 0]

This is the whole design decision. We walk the full input once, but we only keep a pair when the value is not zero. So a vector that is mostly zeros shrinks down to a tiny list of (index, value) pairs. The zeros never get stored.

total = 0
i, j = 0, 0

We start the answer at zero. We place one pointer at the start of each vector’s pair list. i walks our pairs, j walks the other vector’s pairs.

while i < len(self.pairs) and j < len(other.pairs):
    idx_a, val_a = self.pairs[i]
    idx_b, val_b = other.pairs[j]

We keep going while both lists still have pairs left. Each step we read the index and value at both pointers.

    if idx_a == idx_b:
        total += val_a * val_b
        i += 1
        j += 1

When the two indices match, both vectors have a real value at that same position. That is the only case that adds to the dot product. We multiply the two values, add to the total, then move both pointers since this position is done.

    elif idx_a < idx_b:
        i += 1
    else:
        j += 1

When the indices differ, the smaller index is a position where one vector has a value and the other has a zero. A zero contributes nothing. So we just move the pointer that is behind, to catch it up. We never waste a multiplication on a zero. That is why this beats scanning the full vectors.

⏱️ Time and Space Complexity

The brute force stores both full vectors, so the space is O(n) where n is the full length. It scans every position, so the time is O(n) too. The sparse version stores only the non-zero counts. Call them L1 and L2. The space is O(L1 + L2), which is tiny when the vector is mostly zeros. The two-pointer walk visits each pair once, so the time is O(L1 + L2). When most values are zero, that is a huge saving over O(n).

🧩 Key Takeaways

• ✅ A sparse vector is mostly zeros, so storing all the zeros wastes memory and time.
• ✅ Store only the non-zero entries as (index, value) pairs.
• ✅ Take the dot product by walking both pair lists with two pointers, since they are sorted by index.
• ✅ Only matching indices add to the answer, because a zero times anything is zero.
• ✅ This drops the cost from O(n) to O(number of non-zero values), a big win for sparse data.

🚀 What’s Next?

• Design Tic-Tac-Toe
• Nested List Weight Sum