⚡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