Problem of The Day: Insert into a Binary Search Tree

Problem Statement

leetcode problem link

Brute Force [TLE]

class FindSumPairs:
    def helper(self):
        # print('start')
        self.counter2 = Counter(self.nums2)
        # print(self.counter1)
        # print(self.counter2)
        self.pair_count = defaultdict(int)
        seen = set()
        for k1, v1 in self.counter1.items():
            for k2, v2 in self.counter2.items():
                sum_key = k1 + k2
                if (k1, k2) not in seen:
                    self.pair_count[sum_key] += v1 * v2
                    seen.add((k1, k2))
                    # print(sum_key, k1, k2, self.pair_count[sum_key])

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1[:]
        self.nums2 = nums2[:]
        self.counter1 = Counter(nums1)
        self.helper()


    def add(self, index: int, val: int) -> None:
        self.nums2[index] += val
        self.helper()


    def count(self, tot: int) -> int:
        if tot in self.pair_count:
            return self.pair_count[tot]
        return 0



# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

Other Approach [TLE]

class FindSumPairs:
    def helper(self):
        self.counter2 = Counter(self.nums2)

    def __init__(self, nums1: List[int], nums2: List[int]):
        self.nums1 = nums1[:]
        self.nums2 = nums2[:]
        self.counter1 = Counter(nums1)
        self.counter2 = Counter(nums2)
        self.helper()


    def add(self, index: int, val: int) -> None:
        self.nums2[index] += val
        self.helper()


    def count(self, tot: int) -> int:
        res = 0
        seen = set()
        for num1 in self.nums1:
            num2 = tot - num1
            if num2 in self.counter2 and (num1, num2) not in seen:
                res += self.counter1[num1] * self.counter2[num2]
            seen.add((num1, num2))
        return res



# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

Improved Approach [Accepted]

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


    def add(self, index: int, val: int) -> None:
        self.counter2[self.nums2[index]] -= 1
        self.nums2[index] += val
        self.counter2[self.nums2[index]] += 1


    def count(self, tot: int) -> int:
        res = 0
        seen = set()
        for num1 in self.nums1:
            num2 = tot - num1
            if num2 in self.counter2 and num2 not in seen:
                res += self.counter1[num1] * self.counter2[num2]
            seen.add(num2)
        return res



# Your FindSumPairs object will be instantiated and called as such:
# obj = FindSumPairs(nums1, nums2)
# obj.add(index,val)
# param_2 = obj.count(tot)

Editorial

Approach: Hash table

class FindSumPairs:

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

    def add(self, index: int, val: int) -> None:
        _nums2, _cnt = self.nums2, self.cnt

        _cnt[_nums2[index]] -= 1
        _nums2[index] += val
        _cnt[_nums2[index]] += 1

    def count(self, tot: int) -> int:
        _nums1, _cnt = self.nums1, self.cnt

        ans = 0
        for num in _nums1:
            if (rest := tot - num) in _cnt:
                ans += _cnt[rest]
        return ans