Documentation Index
Fetch the complete documentation index at: /llms.txt
Use this file to discover all available pages before exploring further.
Tested Python solution for LeetCode 1570 with 16 pytest cases. Generate a practice environment with lcpy.
lcpy gen -n 1570 # by problem number
lcpy gen -s dot_product_of_two_sparse_vectors # by problem name
SparseVector:
SparseVector(nums) Initializes the object with the vector numsdotProduct(vec) Compute the dot product between the instance of SparseVector and vecInput: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1), v2 = SparseVector(nums2)
v1.dotProduct(v2) = 1*0 + 0*3 + 0*0 + 2*4 + 3*0 = 8
Input: nums1 = [0,1,0,0,0], nums2 = [0,0,0,0,2]
Output: 0
Explanation: v1 = SparseVector(nums1), v2 = SparseVector(nums2)
v1.dotProduct(v2) = 0*0 + 1*0 + 0*0 + 0*0 + 0*2 = 0
Input: nums1 = [0,1,0,0,2,0,0], nums2 = [1,0,0,0,3,0,4]
Output: 6
n == nums1.length == nums2.length1 <= n <= 10^50 <= nums1[i], nums2[i] <= 100from __future__ import annotations
class SparseVector:
# Time: O(n)
# Space: O(k)
def __init__(self, nums: list[int]) -> None:
self.nonzero = {i: v for i, v in enumerate(nums) if v}
# Time: O(min(k1, k2))
# Space: O(1)
def dot_product(self, vec: SparseVector) -> int:
a, b = self.nonzero, vec.nonzero
if len(b) < len(a):
a, b = b, a
return sum(v * b.get(i, 0) for i, v in a.items())
| Time | Space |
|---|---|
| O(n) | O(k) |