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
- 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.
dotProductiterates the smaller of the two non-zero maps and checks membership in the other.- Multiplying zeros is wasted work, so skipping them is the entire optimisation.
- 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.
🧩 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) > len(vec.d): return vec.dotProduct(self) 在两者长度相等时不递归,因此会终止。若写成 >= 则会无限递归。
- 用 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)