Problem Breakdown
We need to compute the scalar (dot) product efficiently. The vectors are sparse, meaning most elements are zero. Storing all elements in a dense array wastes memory ( space). We should store only non-zero values to reduce space complexity to where is the number of non-zeros.
Inputs: Two integer arrays nums representing vector components, length .
Outputs: A single integer (dot product sum).
Constraints:
- Values .
- Time limit requires avoiding unnecessary iterations over zero-filled regions.
Intuition
A naive dense array approach uses space and time for dot product (). While linear, it ignores sparsity in storage.
Optimization Strategy: Use a Hash Map (Dictionary) to store {index: value} pairs only where value != 0. This reduces initialization cost proportional to non-zeros rather than total length if we process input efficiently, and drastically improves query time when vectors are sparse.
Dot Product Logic: The dot product is the sum of products at indices present in both vectors. If an index exists in one vector but not the other (sparse), its contribution is 0 ().
We iterate over the non-zero elements of self and check if they exist in vec. To optimize, we should always iterate over the dictionary with fewer keys to minimize loop overhead.
Approach
- Initialization (
__init__): Iterate through input arraynums. Ifval != 0, store{index: val}in a hash map. Ignore zeros completely. This ensures space usage where is count of non-zeros. - Dot Product (
dotProduct):- Retrieve the internal maps for both vectors.
- Determine which vector has fewer non-zero elements (smaller dictionary).
- Iterate over keys of the smaller map. For each key, check existence in the larger map using
.get()orin. - Accumulate product if index exists; otherwise contribution is 0.
- Follow-up: If one vector were dense (not a SparseVector instance), we would iterate over its non-zeros against the sparse map’s keys, effectively treating it as having zeros implicitly or iterating up to . Since our class enforces sparsity storage, both are treated uniformly.
Complexity Analysis
- Time:
- Initialization: (must read input array once). In practice often optimized by reading chunks if streamable, but here we scan full list.
- Dot Product: Let and be non-zero counts. We iterate . Dictionary lookup is average . Total query time: .
- Space:
- Storage depends on sparsity. Worst case (dense vector): space for the map. Best case (all zeros): auxiliary space beyond input storage overhead.
Solution
from typing import List
class SparseVector:
def __init__(self, nums: List[int]):
# Store only non-zero elements to save memory and time during dot product calculation
self.data = {i: val for i, val in enumerate(nums) if val != 0}
def dotProduct(self, vec: 'SparseVector') -> int:
result = 0
# Optimization: Iterate over the smaller dictionary's keys to minimize loop iterations.
# This ensures O(min(K1, K2)) complexity for the query phase.
if len(self.data) < len(vec.data):
self_iter_data = self.data.items()
other_data = vec.data
else:
self_iter_data = vec.data.items()
other_data = self.data
# Iterate over keys of the smaller map and check existence in the larger map
for index, val_self in self_iter_data:
if index in other_data:
result += val_self * other_data[index]
return result
Edge Cases Handled
- All Zeros: The
datadictionary will be empty. Iteration over an empty dict results in 0, which is the correct dot product for all-zero vectors (sum of zeros). - Dense Vectors (Worst Case): If inputs are dense (), complexity degrades to time and space, matching standard array behavior but still valid within constraints.
- Non-Overlapping Non-Zeros: Indices present in one vector but not the other contribute 0 naturally because
if index in other_dataevaluates to false (or.get()returns default). - Empty Input Lists: Constraints say , so lists are never empty, but logic holds if they were.