Dot Product of Two Sparse Vectors

Was this helpful?

Medium•math•Expected: O(min(k1, k2) time, O(k1 + k2) space

hash-map

Problem

Design a class that takes a sparse vector and computes the dot product with another sparse vector efficiently.

Example 1:

Input: nums1 = [1, 0, 0, 2, 3], nums2 = [0, 3, 0, 4, 0]
Output: 8
Explanation: 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8

Example 2:

Input: nums1 = [0, 1, 0, 0, 0], nums2 = [0, 0, 0, 0, 2]
Output: 0

Reference solution unlocks after your first submission

Language: