Welcome to Subscribe On Youtube

1570. Dot Product of Two Sparse Vectors

Description

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

Solutions

  • class SparseVector {
        public Map<Integer, Integer> d = new HashMap<>(128);
    
        SparseVector(int[] nums) {
            for (int i = 0; i < nums.length; ++i) {
                if (nums[i] != 0) {
                    d.put(i, nums[i]);
                }
            }
        }
    
        // Return the dotProduct of two sparse vectors
        public int dotProduct(SparseVector vec) {
            var a = d;
            var b = vec.d;
            if (b.size() < a.size()) {
                var t = a;
                a = b;
                b = t;
            }
            int ans = 0;
            for (var e : a.entrySet()) {
                int i = e.getKey(), v = e.getValue();
                ans += v * b.getOrDefault(i, 0);
            }
            return ans;
        }
    }
    
    // Your SparseVector object will be instantiated and called as such:
    // SparseVector v1 = new SparseVector(nums1);
    // SparseVector v2 = new SparseVector(nums2);
    // int ans = v1.dotProduct(v2);
    
  • class SparseVector {
    public:
        unordered_map<int, int> d;
    
        SparseVector(vector<int>& nums) {
            for (int i = 0; i < nums.size(); ++i) {
                if (nums[i]) {
                    d[i] = nums[i];
                }
            }
        }
    
        // Return the dotProduct of two sparse vectors
        int dotProduct(SparseVector& vec) {
            auto a = d;
            auto b = vec.d;
            if (a.size() > b.size()) {
                swap(a, b);
            }
            int ans = 0;
            for (auto& [i, v] : a) {
                if (b.count(i)) {
                    ans += v * b[i];
                }
            }
            return ans;
        }
    };
    
    // Your SparseVector object will be instantiated and called as such:
    // SparseVector v1(nums1);
    // SparseVector v2(nums2);
    // int ans = v1.dotProduct(v2);
    
  • class SparseVector:
        def __init__(self, nums: List[int]):
            self.d = {i: v for i, v in enumerate(nums) if v}
    
        # Return the dotProduct of two sparse vectors
        def dotProduct(self, vec: "SparseVector") -> int:
            a, b = self.d, vec.d
            if len(b) < len(a):
                a, b = b, a
            return sum(v * b.get(i, 0) for i, v in a.items())
    
    
    # Your SparseVector object will be instantiated and called as such:
    # v1 = SparseVector(nums1)
    # v2 = SparseVector(nums2)
    # ans = v1.dotProduct(v2)
    
    
  • type SparseVector struct {
    	d map[int]int
    }
    
    func Constructor(nums []int) SparseVector {
    	d := map[int]int{}
    	for i, x := range nums {
    		if x != 0 {
    			d[i] = x
    		}
    	}
    	return SparseVector{d}
    }
    
    // Return the dotProduct of two sparse vectors
    func (this *SparseVector) dotProduct(vec SparseVector) (ans int) {
    	a, b := this.d, vec.d
    	if len(a) > len(b) {
    		a, b = b, a
    	}
    	for i, x := range a {
    		if y, has := b[i]; has {
    			ans += x * y
    		}
    	}
    	return
    }
    
    /**
     * Your SparseVector object will be instantiated and called as such:
     * v1 := Constructor(nums1);
     * v2 := Constructor(nums2);
     * ans := v1.dotProduct(v2);
     */
    
  • class SparseVector {
        d: Map<number, number>;
    
        constructor(nums: number[]) {
            this.d = new Map();
            for (let i = 0; i < nums.length; ++i) {
                if (nums[i] != 0) {
                    this.d.set(i, nums[i]);
                }
            }
        }
    
        // Return the dotProduct of two sparse vectors
        dotProduct(vec: SparseVector): number {
            let a = this.d;
            let b = vec.d;
            if (a.size > b.size) {
                [a, b] = [b, a];
            }
            let ans = 0;
            for (const [i, x] of a) {
                if (b.has(i)) {
                    ans += x * b.get(i)!;
                }
            }
            return ans;
        }
    }
    
    /**
     * Your SparseVector object will be instantiated and called as such:
     * var v1 = new SparseVector(nums1)
     * var v2 = new SparseVector(nums1)
     * var ans = v1.dotProduct(v2)
     */
    
    

All Problems

All Solutions