⚡Flashcard Drill➔
NeetCode #159LC-1570MediumArrays & Hashing
← Back to All Problems

#159 · #1570 · Dot Product of Two Sparse Vectors(两个稀疏向量的点积)

📌 Problem Statement & Constraints

Design a class that computes the dot product of two sparse vectors. The constructor takes nums, and dotProduct(vec) returns the dot product with another sparse vector. Constraints: 1 <= nums.length <= 10^5, 0 <= nums[i] <= 100; the number of non-zero elements is small.

💡 Core Algorithmic Approaches

  1. Store only the non-zero entries as a map from index to value. This makes both memory and iteration proportional to the number of non-zeros.
  2. dotProduct iterates the smaller of the two non-zero maps and checks membership in the other.
  3. Multiplying zeros is wasted work, so skipping them is the entire optimisation.
  4. Iterating the smaller map matters when one vector is much denser than the other.

💻 Benchmark Python3 Implementation

class SparseVector:
    def __init__(self, nums: List[int]):
        self.nz = {i: v for i, v in enumerate(nums) if v}   # only non-zeros

    def dotProduct(self, vec: "SparseVector") -> int:
        # iterate the smaller map for efficiency
        a, b = self.nz, vec.nz
        if len(a) > len(b):
            a, b = b, a
        return sum(v * b[i] for i, v in a.items() if i in b)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(min(nnz1, nnz2)) per dot product, plus O(n) to build each vector.
💾 Space Complexity
O(nnz) per vector.

⚠️ Interview Pitfalls & Follow-ups

  • Storing the full dense array and multiplying element-wise: O(n) per dot product, which the problem explicitly asks you to avoid.
  • Iterating the larger map: correct but slower; iterating the smaller one is the standard trick.
  • Using a list of non-zero values without indices: the index alignment is essential.
  • Ignoring negative values: the constraints here are non-negative, but the sparse representation handles negatives naturally.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems

中文速览与面试要点

两个稀疏向量的点积

给定两个稀疏向量,计算它们的点积(数量积)。请实现类 SparseVector: __init__(nums) 用数组初始化; dotProduct(vec) 计算当前向量与 vec 的点积。点积的定义为: sum(nums1[i] × nums2[i]) 对所有 i。约束:1 ≤ nums.length ≤ 10^5;0 ≤ nums[i] ≤ 100;最多调用 10^4 次 dotProduct。

核心要点

  • 只存非零元素(标准解) :构造函数中把非零元素存成字典 下标: 值 ,空间与「非零元素个数」成正比,而非向量长度。
  • 遍历较小的字典 :点积时遍历元素较少的那个字典,对每个下标检查另一个字典是否有该下标,有则累加乘积。
  • 为什么遍历较小的 :这样哈希查询次数最少,复杂度为 O(min(k1, k2)),k 为非零元素个数。
  • 交换技巧 :若当前字典较大,可交换两者再计算,保证总是遍历较小的那个。

常见陷阱

  • 用完整数组存储 :空间是 O(n),完全违背「稀疏向量」的设计意图。必须只存非零元素。
  • 遍历较长的字典 :哈希查询次数更多,虽然复杂度量级相同但常数更大。
  • 忘记交换技巧导致无限递归 : if len(self.d) &gt; len(vec.d): return vec.dotProduct(self) 在两者长度相等时不递归,因此会终止。若写成 &gt;= 则会无限递归。
  • 用 i in vec.d 之外的方式取值 :直接 vec.d[i] 会在缺失时抛 KeyError,必须先用 in 判断(或用 vec.d.get(i, 0) )。

参考实现

class SparseVector:
    def __init__(self, nums: list[int]):
        # 只保留非零元素:下标 -> 值
        self.d = {i: v for i, v in enumerate(nums) if v != 0}

    def dotProduct(self, vec: 'SparseVector') -> int:
        # 遍历较小的字典,减少哈希查询次数
        if len(self.d) > len(vec.d):
            return vec.dotProduct(self)
        return sum(v * vec.d[i] for i, v in self.d.items() if i in vec.d)