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 sparse vectors.

Examples

Example 1:

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

Constraints

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

Thinking Process

  1. Space efficiency: Store only non-zero elements
  2. Smaller iteration: Always iterate through smaller hash map
  • Identify the pattern from constraints (sorted? graph? optimal substructure?).
  • Write brute force first mentally, then optimize the bottleneck.
  • Verify edge cases: empty input, single element, duplicates.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Brute force (this problem) Often O(n^2) or O(2^n) O(n) Baseline; clarifies the optimization target
Sort + scan O(n log n) O(1) Pairs, intervals, greedy ordering
Hash map / set O(n) O(n) Frequency, membership, two-sum style
Single-pass linear O(n) O(1) Two pointers, sliding window, Kadane

Solution

Time Complexity:

  • Constructor: O(n) where n is the length of the vector
  • dotProduct: O(min(k1, k2)) where k1, k2 are number of non-zero elements

Space Complexity: O(k) where k is the number of non-zero elements

Use a hash map to store only non-zero elements, then optimize dot product by iterating through the smaller hash map.

class SparseVector:
    def __init__(self, nums: list[int]):
        self.cache = {}
        for i, num in enumerate(nums):
            if num != 0:
                self.cache[i] = num

    def dotProduct(self, vec: 'SparseVector') -> int:
        result = 0

        # iterate smaller dictionary for efficiency
        if len(self.cache) <= len(vec.cache):
            smaller, larger = self.cache, vec.cache
        else:
            smaller, larger = vec.cache, self.cache

        for idx, num in smaller.items():
            if idx in larger:
                result += num * larger[idx]

        return result
# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)

Solution Explanation

Key Insight: Store only non-zero elements in a hash map, then optimize dot product by iterating through the smaller hash map.

Steps:

  1. Constructor: Store only non-zero elements with their indices
  2. Dot product: Iterate through smaller hash map and check for matching indices
  3. Optimization: Always iterate through the smaller hash map for efficiency
  4. Return result: Sum of products of matching non-zero elements

Step-by-Step Example

Example: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]

Step 1: Constructor for v1

nums1 = [1,0,0,2,3]
cache1 = {0: 1, 3: 2, 4: 3}

Step 2: Constructor for v2

nums2 = [0,3,0,4,0]
cache2 = {1: 3, 3: 4}

Step 3: Dot Product Calculation

smaller = cache2 = {1: 3, 3: 4}  (size = 2)
larger = cache1 = {0: 1, 3: 2, 4: 3}  (size = 3)

For each element in smaller:
- idx = 1, num = 3: larger[1] = 0 (not found) → skip
- idx = 3, num = 4: larger[3] = 2 → rtn += 4 * 2 = 8

Result = 8

Algorithm Breakdown

Constructor:

def __init__(self, nums: list[int]):
    self.cache = {}
    for i, num in enumerate(nums):
        if num != 0:
            self.cache[i] = num

Process:

  1. Iterate through vector: Check each element
  2. Store non-zero elements: Only store elements that are not zero
  3. Index-value mapping: Map index to value for efficient lookup
  4. Space optimization: Save space by not storing zeros

Dot Product:

def dotProduct(self, vec: 'SparseVector') -> int:
    result = 0

    # iterate smaller dictionary for efficiency
    if len(self.cache) <= len(vec.cache):
        smaller, larger = self.cache, vec.cache
    else:
        smaller, larger = vec.cache, self.cache

    for idx, num in smaller.items():
        if idx in larger:
            result += num * larger[idx]

    return result

Process:

  1. Choose smaller hash map: Optimize by iterating through smaller map
  2. Check for matches: For each index in smaller map, check if it exists in larger map
  3. Calculate product: If match found, multiply values and add to result
  4. Return sum: Total dot product of matching elements

Complexity

| Operation | Time Complexity | Space Complexity | |———–|—————-|——————| | Constructor | O(n) | O(k) | | dotProduct | O(min(k1, k2)) | O(1) | | Total | O(n + min(k1, k2)) | O(k1 + k2) |

Where n is the length of the vector, k1 and k2 are the number of non-zero elements in each vector.

Detailed Example Walkthrough

Example: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]

Step 1: Constructor for v1

nums1 = [0,1,0,0,2,0,0]
cache1 = {1: 1, 4: 2}

Step 2: Constructor for v2

nums2 = [1,0,0,0,3,0,4]
cache2 = {0: 1, 4: 3, 6: 4}

Step 3: Dot Product Calculation

smaller = cache1 = {1: 1, 4: 2}  (size = 2)
larger = cache2 = {0: 1, 4: 3, 6: 4}  (size = 3)

For each element in smaller:
- idx = 1, num = 1: larger[1] = 0 (not found) → skip
- idx = 4, num = 2: larger[4] = 3 → rtn += 2 * 3 = 6

Result = 6

Common Mistakes

  1. All zeros: nums1 = [0,0,0], nums2 = [0,0,0] → 0
  2. Single non-zero: nums1 = [1,0,0], nums2 = [0,0,1] → 0
  3. No matches: nums1 = [1,0,0], nums2 = [0,1,0] → 0

  4. Perfect match: nums1 = [1,2,3], nums2 = [1,2,3] → 14

  5. Not optimizing iteration: Always iterate through smaller hash map
  6. Missing zero check: Not checking if index exists in larger map
  7. Wrong index mapping: Confusing index with value
  8. Inefficient storage: Storing all elements including zeros

Why This Solution Works

Hash Map Optimization:

  1. Space efficiency: Store only non-zero elements
  2. Fast lookup: O(1) access to non-zero elements
  3. Index preservation: Maintain original indices for dot product
  4. Memory trade-off: Use extra space for faster operations

Dot Product Optimization:

  1. Smaller iteration: Always iterate through smaller hash map
  2. Match checking: Check if index exists in larger hash map
  3. Product calculation: Multiply matching values
  4. Efficient computation: Avoid unnecessary iterations

Key Algorithm Properties:

  1. Correctness: Always produces valid result
  2. Efficiency: O(min(k1, k2)) dot product complexity
  3. Space optimization: Only stores non-zero elements
  4. Simplicity: Easy to understand and implement

References

Key Takeaways

Hash Map Optimization:

  1. Space efficiency: Store only non-zero elements
  2. Fast lookup: O(1) access to non-zero elements
  3. Index preservation: Maintain original indices for dot product
  4. Memory trade-off: Use extra space for faster operations

Dot Product Optimization:

  1. Smaller iteration: Always iterate through smaller hash map
  2. Match checking: Check if index exists in larger hash map
  3. Product calculation: Multiply matching values
  4. Efficient computation: Avoid unnecessary iterations