How hard is LeetCode 1570. Dot Product of Two Sparse Vectors?

LeetCode 1570. Dot Product of Two Sparse Vectors is rated Medium on LeetCode.

What is the time complexity of LeetCode 1570. Dot Product of Two Sparse Vectors?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1570. Dot Product of Two Sparse Vectors?

The Python solution on this page uses O(n), where n is the length of the array auxiliary space.

What topics does LeetCode 1570. Dot Product of Two Sparse Vectors cover?

LeetCode 1570. Dot Product of Two Sparse Vectors is tagged Design, Array, Hash Table and Two Pointers on LeetCode.

Is LeetCode 1570. Dot Product of Two Sparse Vectors a premium problem?

Yes. LeetCode 1570. Dot Product of Two Sparse Vectors is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Dot Product of Two Sparse Vectors — LeetCode 1570 Python Solution

MediumLeetCode PremiumDesignArrayHash TableTwo Pointers

Problem: #1570
Pattern: Two Pointers
Reading time: 3 min
Source: leetcode.com

The problem

Given two sparse vectors, compute their dot product. Implement class SparseVector: SparseVector(nums) Initializes the object with the vector nums dotProduct(vec) Compute the dot product between the instance of SparseVector and vec A sparse vector is a vector that has mostly zero values, you should store the sparse vector efficiently and compute the dot product between two SparseVector.

Example

Input: nums1 = [1,0,0,2,3], nums2 = [0,3,0,4,0]
Output: 8
Explanation: v1 = SparseVector(nums1) , v2 = SparseVector(nums2)

Python solution

Python

class SparseVector:
    def __init__(self, nums: List[int]):
        self.d = {i: v for i, v in enumerate(nums) if v}

    # Return the dotProduct of two sparse vectors
    def dotProduct(self, vec: "SparseVector") -> int:
        a, b = self.d, vec.d
        if len(b) < len(a):
            a, b = b, a
        return sum(v * b.get(i, 0) for i, v in a.items())


# Your SparseVector object will be instantiated and called as such:
# v1 = SparseVector(nums1)
# v2 = SparseVector(nums2)
# ans = v1.dotProduct(v2)

Complexity

Measure	Complexity
Time	O(n)
Space	O(n), where n is the length of the array auxiliary

Pattern: Two Pointers

Use the order already in the input to discard half the search space at every step. LeetCode 1570. Dot Product of Two Sparse Vectors is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.

The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1570. Dot Product of Two Sparse Vectors?: LeetCode 1570. Dot Product of Two Sparse Vectors is rated Medium on LeetCode.
What is the time complexity of LeetCode 1570. Dot Product of Two Sparse Vectors?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1570. Dot Product of Two Sparse Vectors?: The Python solution on this page uses O(n), where n is the length of the array auxiliary space.
What topics does LeetCode 1570. Dot Product of Two Sparse Vectors cover?: LeetCode 1570. Dot Product of Two Sparse Vectors is tagged Design, Array, Hash Table and Two Pointers on LeetCode.
Is LeetCode 1570. Dot Product of Two Sparse Vectors a premium problem?: Yes. LeetCode 1570. Dot Product of Two Sparse Vectors is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.