Problem statement

https://leetcode.com/problems/dot-product-of-two-sparse-vectors/

Solution

All we need to do is for every vector keep only dictionary of non-zero coordinates. Then we iterate throuhg them and check only those we need.

Complexity

Time complexity for init is O(n), where n is length of vector. Time complexity of dotProduct is O(A + B), where A and B are numbers of non-zero elements.

Code

class SparseVector:
	def __init__(self, A):
		self.m = {i: x for i, x in enumerate(A) if x}
        
	def dotProduct(self, vec):
		return sum([x * self.m.get(i, 0) for i, x in vec.m.items()])