350. Dot Product of Two Sparse Vectors

Store just the non-zero entries of the first vector as index -> value. Then scan the second vector's non-zeros and multiply only where the first vector also has a non-zero.

Skip the zeros

A sparse vector wastes time if you iterate every index. Instead, record the non-zero entries of nums1 in a map index -> value. Then for each non-zero of nums2, add map[index] * value when the index is present.

nonzero = {i: v for i, v in enumerate(nums1) if v != 0}
total = sum(nonzero[i] * v for i, v in enumerate(nums2) if v and i in nonzero)

Worked example

[1,0,0,2,3] · [0,3,0,4,0] → only index 3 overlaps non-zero: 2*4 = 8.

Complexity

• Time: O(n) to build, O(nnz) to combine.
• Space: O(nnz).

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int dotProduct(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nonzero = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            if (nums1[i] != 0) nonzero.put(i, nums1[i]);
        }
        int total = 0;
        for (int i = 0; i < nums2.length; i++) {
            if (nums2[i] != 0 && nonzero.containsKey(i)) {
                total += nonzero.get(i) * nums2[i];
            }
        }
        return total;
    }
}