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.