Domain 2MediumMEDIUM

Dot Product of Two Sparse Vectors

Compute dot product of two sparse vectors by storing non-zero elements in hash maps and iterating over the smaller set for efficiency.

Domain: medium•Updated: 2026-09-18
#hash map#sparse vector#O(min(K, N)) time complexity

Problem Breakdown

We need to compute the scalar (dot) product ∑i=0n−1nums1[i]×nums2[i]\sum_{i=0}^{n-1} nums1[i] \times nums2[i] efficiently. The vectors are sparse, meaning most elements are zero. Storing all NN elements in a dense array wastes memory (O(N)O(N) space). We should store only non-zero values to reduce space complexity to O(K)O(K) where KK is the number of non-zeros.

Inputs: Two integer arrays nums representing vector components, length NN. Outputs: A single integer (dot product sum). Constraints:

  • 1≤N≤1051 \le N \le 10^5
  • Values ≥0\ge 0.
  • Time limit requires avoiding unnecessary iterations over zero-filled regions.

Intuition

A naive dense array approach uses O(N)O(N) space and time for dot product (O(N)O(N)). While linear, it ignores sparsity in storage. Optimization Strategy: Use a Hash Map (Dictionary) to store {index: value} pairs only where value != 0. This reduces initialization cost proportional to non-zeros rather than total length if we process input efficiently, and drastically improves query time when vectors are sparse. Dot Product Logic: The dot product is the sum of products at indices present in both vectors. If an index exists in one vector but not the other (sparse), its contribution is 0 (x×0=0x \times 0 = 0). We iterate over the non-zero elements of self and check if they exist in vec. To optimize, we should always iterate over the dictionary with fewer keys to minimize loop overhead.

Approach

  1. Initialization (__init__): Iterate through input array nums. If val != 0, store {index: val} in a hash map. Ignore zeros completely. This ensures O(K)O(K) space usage where KK is count of non-zeros.
  2. Dot Product (dotProduct):
    • Retrieve the internal maps for both vectors.
    • Determine which vector has fewer non-zero elements (smaller dictionary).
    • Iterate over keys of the smaller map. For each key, check existence in the larger map using .get() or in.
    • Accumulate product if index exists; otherwise contribution is 0.
  3. Follow-up: If one vector were dense (not a SparseVector instance), we would iterate over its non-zeros against the sparse map’s keys, effectively treating it as having NN zeros implicitly or iterating up to min⁡(Ndense,Ksparse)\min(N_{dense}, K_{sparse}). Since our class enforces sparsity storage, both are treated uniformly.

Complexity Analysis

  • Time:
    • Initialization: O(N)O(N) (must read input array once). In practice often optimized by reading chunks if streamable, but here we scan full list.
    • Dot Product: Let K1K_1 and K2K_2 be non-zero counts. We iterate min⁡(K1,K2)\min(K_1, K_2). Dictionary lookup is average O(1)O(1). Total query time: O(min⁡(K1,K2))O(\min(K_1, K_2)).
  • Space:
    • Storage depends on sparsity. Worst case (dense vector): O(N)O(N) space for the map. Best case (all zeros): O(1)O(1) auxiliary space beyond input storage overhead.

Solution

from typing import List

class SparseVector:
    def __init__(self, nums: List[int]):
        # Store only non-zero elements to save memory and time during dot product calculation
        self.data = {i: val for i, val in enumerate(nums) if val != 0}

    def dotProduct(self, vec: 'SparseVector') -> int:
        result = 0
        
        # Optimization: Iterate over the smaller dictionary's keys to minimize loop iterations.
        # This ensures O(min(K1, K2)) complexity for the query phase.
        if len(self.data) < len(vec.data):
            self_iter_data = self.data.items()
            other_data = vec.data
        else:
            self_iter_data = vec.data.items()
            other_data = self.data
            
        # Iterate over keys of the smaller map and check existence in the larger map
        for index, val_self in self_iter_data:
            if index in other_data:
                result += val_self * other_data[index]
                
        return result

Edge Cases Handled

  • All Zeros: The data dictionary will be empty. Iteration over an empty dict results in 0, which is the correct dot product for all-zero vectors (sum of zeros).
  • Dense Vectors (Worst Case): If inputs are dense (K≈NK \approx N), complexity degrades to O(N)O(N) time and space, matching standard array behavior but still valid within constraints.
  • Non-Overlapping Non-Zeros: Indices present in one vector but not the other contribute 0 naturally because if index in other_data evaluates to false (or .get() returns default).
  • Empty Input Lists: Constraints say 1≤n1 \le n, so lists are never empty, but logic holds if they were.