Code Implementation

class SparseVector:
    def __init__(self, nums):
        # Store non-zero elements as {index: value}
        self.nonzero = {i: num for i, num in enumerate(nums) if num != 0}

    def dotProduct(self, vec):
        # Only iterate over the smaller set of non-zero elements
        if len(self.nonzero) > len(vec.nonzero):
            return vec.dotProduct(self)
        res = 0
        for i, v in self.nonzero.items():
            res += v * vec.nonzero.get(i, 0)
        return res
      

class SparseVector {
public:
    unordered_map<int, int> nonzero;
    SparseVector(vector<int> &nums) {
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] != 0) {
                nonzero[i] = nums[i];
            }
        }
    }
    int dotProduct(SparseVector &vec) {
        // Iterate over the smaller map
        if (nonzero.size() > vec.nonzero.size()) {
            return vec.dotProduct(*this);
        }
        int res = 0;
        for (auto &p : nonzero) {
            int idx = p.first;
            int val = p.second;
            if (vec.nonzero.count(idx)) {
                res += val * vec.nonzero.at(idx);
            }
        }
        return res;
    }
};
      

class SparseVector {
    private Map<Integer, Integer> nonzero;
    public SparseVector(int[] nums) {
        nonzero = new HashMap<>();
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] != 0) {
                nonzero.put(i, nums[i]);
            }
        }
    }
    // Return the dotProduct of two sparse vectors
    public int dotProduct(SparseVector vec) {
        if (this.nonzero.size() > vec.nonzero.size()) {
            return vec.dotProduct(this);
        }
        int res = 0;
        for (Map.Entry<Integer, Integer> entry : this.nonzero.entrySet()) {
            int idx = entry.getKey();
            int val = entry.getValue();
            res += val * vec.nonzero.getOrDefault(idx, 0);
        }
        return res;
    }
}
      

class SparseVector {
    constructor(nums) {
        this.nonzero = new Map();
        for (let i = 0; i < nums.length; ++i) {
            if (nums[i] !== 0) {
                this.nonzero.set(i, nums[i]);
            }
        }
    }
    dotProduct(vec) {
        // Iterate over the smaller map
        let a = this.nonzero, b = vec.nonzero;
        if (a.size > b.size) {
            return vec.dotProduct(this);
        }
        let res = 0;
        for (let [i, v] of a) {
            res += v * (b.get(i) || 0);
        }
        return res;
    }
}
      

Problem Description

You are given two vectors represented as integer arrays, nums1 and nums2, that can be very large but are sparse (most elements are zero). Your task is to efficiently compute their dot product, which is defined as the sum of products of corresponding elements: nums1[0]*nums2[0] + nums1[1]*nums2[1] + ....

The challenge is to avoid unnecessary computation and memory usage by taking advantage of the sparsity. You should design a class SparseVector that supports:

• Initialization from a vector (array) of integers
• A dotProduct method that takes another SparseVector and returns the dot product as an integer

• Both input vectors can be very large (up to 10⁵ elements or more)
• Most elements are zero, so efficiency is key
• Only non-zero elements contribute to the dot product
• Do not use brute-force iteration over the entire array

Thought Process

At first glance, you might consider iterating over both arrays and multiplying corresponding elements. However, since most elements are zero, this would waste both time and memory. Instead, notice that only the positions where both vectors are non-zero matter for the dot product.

We can exploit this sparsity by storing only the non-zero elements and their indices. This way, we can skip all the zero multiplications, which do not affect the result. If we store non-zero elements in a hash map (index → value), we can quickly check if the other vector also has a non-zero value at that index.

To further optimize, we can iterate over the smaller set of non-zero indices to minimize the number of lookups and multiplications.

Solution Approach

Here’s a step-by-step plan to solve the problem efficiently:

1. Store Non-Zero Elements: When initializing a SparseVector, scan through the input array and record each non-zero element and its index in a hash map or dictionary. This reduces storage and allows fast lookups.
2. Efficient Dot Product: To calculate the dot product, iterate over the non-zero elements of the vector with fewer non-zeros (to minimize work). For each index, check if the other vector also has a non-zero value at that index. If so, multiply the values and add to the result.
3. Return the Sum: After processing all relevant indices, return the accumulated sum as the dot product.

This approach is efficient because:

• It only processes non-zero elements, skipping all zeros.
• Hash map lookups are fast (average-case O(1)).
• Iterating over the smaller set of non-zeros reduces time further.

Example Walkthrough

Example:
nums1 = [1, 0, 0, 2, 3]
nums2 = [0, 3, 0, 4, 0]

1. Initialization:
   • SparseVector(nums1) stores: {0: 1, 3: 2, 4: 3}
   • SparseVector(nums2) stores: {1: 3, 3: 4}
2. Dot Product Calculation:
   • Iterate over the smaller map (nums2: {1: 3, 3: 4})
   • Index 1: nums1 has 0 (not stored), skip
   • Index 3: nums1 has 2, nums2 has 4, multiply: 2 * 4 = 8
3. Sum Up:
   • Only one non-zero product: 8
   • Return 8 as the dot product

Time and Space Complexity

Brute-force Approach:

• Time: O(N), where N is the length of the vectors (since you check every element)
• Space: O(1) extra (not counting input), but inefficient if N is large and sparse

• Time: O(M), where M is the number of non-zero elements (much smaller than N)
• Space: O(M) for storing the non-zero elements in a hash map

The optimized approach is significantly faster and more memory-efficient for large, sparse vectors.

Summary

By representing sparse vectors with hash maps of non-zero elements, we can compute their dot product efficiently by iterating only over the relevant indices. This avoids unnecessary computation and leverages the data's sparsity. The approach is elegant because it reduces both time and space complexity, making it suitable for very large vectors with few non-zero entries.