1570. Dot Product of Two Sparse Vectors

1570. Dot Product of Two Sparse Vectors (Medium)

Given two sparse vectors, compute their dot product.

Implement class SparseVector:

• SparseVector(nums) Initializes the object with the vector nums
• dotProduct(vec) Compute the dot product between the instance of SparseVector and vec

A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Follow up: What if only one of the vectors is sparse?

 

Example 1:

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 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
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0

Example 3:

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

 

Constraints:

• n == nums1.length == nums2.length
• 1 <= n <= 10^5
• 0 <= nums1[i], nums2[i] <= 100

Companies:
Facebook, Microsoft

Related Topics:
Array, Hash Table, Two Pointers

Solution 1.

// OJ: https://leetcode.com/problems/dot-product-of-two-sparse-vectors/
// Author: github.com/lzl124631x
// Time:
//      SparseVector: O(NlogN)
//      dotProduct: O(min(A, B));
// Space: O(M) where M is the number of non-zero values in the input array
class SparseVector {
    map<int, int> m;
public:
    SparseVector(vector<int> &A) {
        for (int i = 0; i < A.size(); ++i) {
            if (A[i]) m[i] = A[i];
        }
    }
    int dotProduct(SparseVector& vec) {
        int ans = 0;
        for (auto a = m.begin(), b = vec.m.begin(); a != m.end() && b != vec.m.end(); ) {
            if (a->first < b->first) ++a;
            else if (a->first > b->first) ++b;
            else {
                ans += a->second * b->second;
                ++a;
                ++b;
            }
        }
        return ans;
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/dot-product-of-two-sparse-vectors/
// Author: github.com/lzl124631x
// Time:
//      SparseVector: O(N)
//      dotProduct: O(A)
// Space: O(M) where M is the number of non-zero values in the input array
class SparseVector {
    unordered_map<int, int> m;
public:
    SparseVector(vector<int> &A) {
        for (int i = 0; i < A.size(); ++i) {
            if (A[i]) m[i] = A[i];
        }
    }
    int dotProduct(SparseVector& vec) {
        int ans = 0;
        for (auto &[index, val] : m) {
            if (vec.m.count(index)) ans += val * vec.m[index];
        }
        return ans;
    }
};