1570.md

1570. Dot Product of Two Sparse Vectors

Level:

Topic:

Question

Given two sparse vectors, compute their dot product. 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.

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) = 10 + 03 + 00 + 24 + 3*0 = 8

Intuition

• Use hashmap to store only the non zero integer with their index
• compute the product if both vector's index are non zero

Code

Time: O(n)
Space: O(L) for nonzero elements

class SparseVector {

    public HashMap<Integer, Integer> map;
    SparseVector(int[] nums) {
        map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0)
                map.put(i, nums[i]);
        }
    }

	// Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        int product = 0;
        HashMap<Integer, Integer> mapVec = vec.map;

        if (mapVec.size() < map.size()) {
            for (int key: mapVec.keySet()) {
                if (map.containsKey(key))
                    product += map.get(key) * mapVec.get(key);
            }
        } else {
            for (int key: map.keySet()) {
                if (mapVec.containsKey(key))
                    product += map.get(key) * mapVec.get(key);
            }
        }

        return product;
    }
}