I store nums1 as-is since it’s small (up to 1000 elements) and won’t change. For nums2, which can be large, I keep a frequency map (Counter) to quickly compute the number of pairs that sum to a given total. Every time I perform an add operation, I update both nums2 and its frequency map in constant time. During a count query, I iterate through nums1 and for each value, I check how many times its complement to tot exists in nums2 using the frequency map.
class FindSumPairs:
def __init__(self, nums1: List[int], nums2: List[int]):
self.nums1 = nums1
self.nums2 = nums2
self.counter2 = Counter(nums2)
def add(self, index: int, val: int) -> None:
old_val = self.nums2[index]
new_val = old_val + val
self.counter2[old_val] -= 1
if self.counter2[old_val] == 0:
del self.counter2[old_val]
self.nums2[index] = new_val
self.counter2[new_val] += 1
def count(self, tot: int) -> int:
count = 0
for a in self.nums1:
target = tot - a
count += self.counter2.get(target, 0)
return count
# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)- Time:
- Space:
