Practice/Meta/Leetcode 1570. Dot Product of Two Sparse Vectors

Leetcode 1570. Dot Product of Two Sparse Vectors

CodingMust

Problem

You are building a machine learning library that needs to handle very large vectors where most elements are zero (sparse vectors). Your task is to design a class that efficiently stores sparse vectors and computes their dot product.

A dot product of two vectors is the sum of the products of their corresponding elements. For example, the dot product of [1, 0, 3] and [4, 2, 1] is 1*4 + 0*2 + 3*1 = 7.

When vectors contain mostly zeros, storing every element wastes memory and computing over all elements wastes time. Your implementation should only store and process non-zero values.

Implement the SparseVector class:

• SparseVector(nums) - Initializes the object with the vector nums
• dotProduct(vec) - Computes the dot product between this vector and vec

Requirements

1. Store the sparse vector efficiently by only keeping track of non-zero elements
2. The dotProduct method should only iterate over non-zero elements, not the entire vector length
3. Handle vectors of any size, including very large vectors (up to 100,000 elements)
4. Return the correct integer result for the dot product

Constraints

• n == nums.length
• 1 <= n <= 100000
• 0 <= nums[i] <= 100
• At most 1000 non-zero elements in each vector
• The dot product computation should be significantly faster than O(n) when the number of non-zero elements is much smaller than n

Examples

Example 1:

Input: nums1 = [1, 0, 0, 2, 3] nums2 = [0, 3, 0, 4, 0] Output: 8 Explanation: The dot product is 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8 Only index 3 has non-zero values in both vectors.

Example 2:

Input: nums1 = [0, 1, 0, 0, 0] nums2 = [0, 0, 0, 0, 2] Output: 0 Explanation: No indices have non-zero values in both vectors.

Example 3:

Input: nums1 = [1, 2, 3] nums2 = [4, 5, 6] Output: 32 Explanation: 1*4 + 2*5 + 3*6 = 4 + 10 + 18 = 32