633. Dot Product of Two Sparse Vectors
A sparse vector is a vector in which almost every entry is zero. You are given two integer vectors nums1 and nums2 of the same length. Return their dot product: the sum of nums1[i] * nums2[i] over every index i.
Because the vectors are sparse, only the positions where both entries are nonzero contribute anything to the sum. A strong solution stores each vector compactly (its nonzero entries only) and computes the product by touching just those entries — that follow-up is what interviewers are really asking about.
Your function receives the two vectors as integer arrays and returns one integer, the dot product.
Example 1:
Input: nums1 = [1, 0, 0, 2, 3], nums2 = [0, 3, 0, 4, 0]
Output: 8
Explanation: Only index 3 has a nonzero entry in both vectors: 2 * 4 = 8. Every other term is multiplied by a zero.
Example 2:
Input: nums1 = [0, 1, 0, 0, 0], nums2 = [0, 0, 0, 0, 2]
Output: 0
Explanation: The nonzero entries live at different indices (1 vs 4), so no pair overlaps and the dot product is 0.
Example 3:
Input: nums1 = [0, 1, 0, 0, 2, 0, 0], nums2 = [1, 0, 0, 0, 3, 0, 4]
Output: 6
Explanation: Index 4 is the only shared nonzero position: 2 * 3 = 6.
Constraints:
- n == nums1.length == nums2.length
- 1 ≤ n ≤ 10⁵
- -100 ≤ nums1[i], nums2[i] ≤ 100
Hints:
A plain loop summing nums1[i] * nums2[i] is correct — but it does work at every index, even where one side is zero. How would you skip the zeros entirely?
Compress each vector into a list of (index, value) pairs for its nonzero entries. The pairs are already sorted by index — walk both lists with two pointers, multiplying only when the indices match.
A hash map from index → value also works for the lookup, but interviewers usually prefer the two-pointer pair lists: no hashing overhead, and it extends cleanly to 'what if only one vector is sparse?' (binary search the longer list).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [1, 0, 0, 2, 3], nums2 = [0, 3, 0, 4, 0]
Expected output: 8