Finding Pairs With a Certain Sum

We are tasked with implementing a class FindSumPairs that can efficiently perform two types of operations: adding a value to a specific index in the array nums2 and counting the number of pairs that sum to a given total. The two arrays are nums1 and nums2.

Here’s how we can implement the class:

Initialization

• Store both arrays.
• Create a counter for the elements in nums2 to efficiently handle updates and counts.

Add

• Update the counter according to the changed value at the specified index in nums2.

Count

• Iterate through nums1 and for each element, check the counter to see how many elements in nums2 can pair with it to make the total.

Here’s the code for the class:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

from collections import Counter

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1
        self.nums2 = nums2
        self.counter_nums2 = Counter(nums2)

    def add(self, index: int, val: int) -> None:
        old_val = self.nums2[index]
        new_val = old_val + val
        self.counter_nums2[old_val] -= 1
        if self.counter_nums2[old_val] == 0:
            del self.counter_nums2[old_val]
        self.counter_nums2[new_val] += 1
        self.nums2[index] = new_val

    def count(self, tot: int) -> int:
        count = 0
        for num in self.nums1:
            count += self.counter_nums2[tot - num]
        return count

Example

• findSumPairs = FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4])
• findSumPairs.count(7) returns 8
• findSumPairs.add(3, 2)
• findSumPairs.count(8) returns 2
• findSumPairs.count(4) returns 1
• findSumPairs.add(0, 1)
• findSumPairs.add(1, 1)
• findSumPairs.count(7) returns 11

Key Takeaway

• Utilizing a counter for nums2 allows for efficient update and count operations.
• By keeping track of the frequency of elements in nums2, we can quickly count pairs without iterating through nums2 for each element in nums1.