Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Only the second array changes, and the first array is small. Store frequencies for the mutable array, then answer a sum query by looking up each first-array value's required complement. A frequency accounts for all matching second-array indices at once.

Approach

Retain both arrays and build a frequency map for nums2. On add(index, val), decrement the old value's frequency, change that array entry, and increment the new value's frequency. On count(tot), sum the frequency of tot - x for every element x in nums1. Repeated first-array values are visited separately, correctly counting distinct index pairs. Missing or zero-frequency complements contribute nothing.

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

        for n in self.nums2:
            self.map2[n] += 1

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

    def count(self, tot: int) -> int:
        cnt = 0

        for n1 in self.nums1:
            curr = tot - n1
            if curr in self.map2:
                cnt += self.map2[curr]

        return cnt

Complexity analysis

Let n = nums1.length, m = nums2.length, and h be the number of distinct values ever held by nums2 so far. Both languages retain zero-count keys; h can exceed the current distinct-value count and is at most u0 + A after A add calls, where u0 is the initial distinct count. Construction takes O(m) expected time, add takes O(1) expected amortized time, and count takes O(n) expected time. Persistent storage is O(n + m + h) including the retained input arrays, or O(h) extra allocated map storage beyond them. Count checks membership before lookup and does not create absent complement keys.