Problem Description

You need to implement a data structure called FindSumPairs that works with two integer arrays nums1 and nums2. This data structure should support two types of operations:

1. Add Operation: Add a positive integer value to an element at a specific index in nums2. Specifically, when you call add(index, val), it performs nums2[index] += val.

2. Count Operation: Count how many pairs (i, j) exist such that nums1[i] + nums2[j] equals a given target value. Here, i can be any valid index in nums1 (from 0 to nums1.length - 1) and j can be any valid index in nums2 (from 0 to nums2.length - 1).

The class should have three methods:

• FindSumPairs(nums1, nums2): Constructor that initializes the object with two integer arrays
• add(index, val): Adds val to the element at position index in nums2
• count(tot): Returns the number of pairs where the sum of one element from nums1 and one element from nums2 equals tot

For example, if nums1 = [1, 1, 2] and nums2 = [2, 3, 4], and you want to count pairs that sum to 5, you would look for all combinations where nums1[i] + nums2[j] = 5. The pairs would be: (1, 4), (1, 4), and (2, 3), giving a count of 3.

The key challenge is handling these operations efficiently, especially since nums2 can be modified through the add operation, which affects subsequent count queries.

Intuition

When we need to count pairs that sum to a target value, the naive approach would be to check every possible pair (i, j) by iterating through both arrays. However, with nums1 having up to 1,000 elements and nums2 having up to 100,000 elements, this would require up to 100 million operations for each count query, which is too slow.

The key observation is the significant size difference between the two arrays. Since nums1 is much smaller (max 1,000 elements) compared to nums2 (max 100,000 elements), we should leverage this asymmetry.

For each element x in nums1, we need to find how many elements in nums2 equal tot - x. Instead of searching through nums2 each time, we can precompute the frequency of each value in nums2 using a hash table. This way, for any value x from nums1, we can instantly look up how many times tot - x appears in nums2.

The beauty of this approach is that:

1. We only iterate through the smaller array (nums1) during count operations
2. We use O(1) hash table lookups instead of O(n) searches in nums2
3. When we modify nums2 with the add operation, we only need to update the frequency count for two values: decrease the count for the old value and increase it for the new value

This transforms what could be an O(n × m) operation into an O(n) operation where n is the size of the smaller array, making the solution much more efficient.

Solution Approach

The solution uses a hash table (Counter in Python) to efficiently track the frequency of elements in nums2. Here's how each component works:

Initialization (__init__ method):

• Store nums1 and nums2 as instance variables for later use
• Create a Counter object cnt that stores the frequency of each element in nums2
• For example, if nums2 = [2, 3, 2, 4], then cnt = {2: 2, 3: 1, 4: 1}

Add Operation (add method): When adding val to nums2[index], we need to maintain the accuracy of our frequency counter:

1. First, decrease the count of the current value: self.cnt[self.nums2[index]] -= 1
   • This removes one occurrence of the old value from our frequency map
2. Update the actual value in the array: self.nums2[index] += val
3. Increase the count of the new value: self.cnt[self.nums2[index]] += 1
   • This adds one occurrence of the new value to our frequency map

This three-step process ensures our frequency counter stays synchronized with the actual array values.

Count Operation (count method): To count pairs that sum to tot:

1. Iterate through each element x in nums1
2. For each x, we need elements from nums2 that equal tot - x
3. Look up cnt[tot - x] to get the number of such elements in nums2
4. Sum all these counts: sum(self.cnt[tot - x] for x in self.nums1)

For example, if tot = 5 and x = 2 from nums1, we look for how many times 3 appears in nums2 (since 2 + 3 = 5).

Time Complexity:

• Initialization: O(m) where m is the length of nums2
• Add: O(1) - just hash table updates
• Count: O(n) where n is the length of nums1

Space Complexity:

• O(m) for storing the frequency counter of nums2

This approach is optimal because it leverages the smaller size of nums1 and uses hash table lookups to avoid repeated iterations through the larger nums2 array.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Initial Setup:

• nums1 = [1, 1, 2, 3]
• nums2 = [2, 3, 3, 4]

When we initialize FindSumPairs, we create a frequency counter for nums2:

• cnt = {2: 1, 3: 2, 4: 1} (value 2 appears once, value 3 appears twice, value 4 appears once)

Operation 1: count(4) We want to find pairs that sum to 4.

• For nums1[0] = 1: We need 4 - 1 = 3 from nums2. Check cnt[3] = 2, so we found 2 pairs
• For nums1[1] = 1: We need 4 - 1 = 3 from nums2. Check cnt[3] = 2, so we found 2 more pairs
• For nums1[2] = 2: We need 4 - 2 = 2 from nums2. Check cnt[2] = 1, so we found 1 pair
• For nums1[3] = 3: We need 4 - 3 = 1 from nums2. Check cnt[1] = 0, so we found 0 pairs

Total: 2 + 2 + 1 + 0 = 5 pairs

Operation 2: add(0, 1) This adds 1 to nums2[0], changing it from 2 to 3.

• Step 1: Decrease count of old value: cnt[2] -= 1, so cnt[2] becomes 0
• Step 2: Update the array: nums2[0] = 2 + 1 = 3, so nums2 = [3, 3, 3, 4]
• Step 3: Increase count of new value: cnt[3] += 1, so cnt[3] becomes 3

Now our frequency counter is: cnt = {2: 0, 3: 3, 4: 1}

Operation 3: count(4) Let's count pairs summing to 4 again with the modified nums2:

• For nums1[0] = 1: We need 4 - 1 = 3 from nums2. Check cnt[3] = 3, so we found 3 pairs
• For nums1[1] = 1: We need 4 - 1 = 3 from nums2. Check cnt[3] = 3, so we found 3 more pairs
• For nums1[2] = 2: We need 4 - 2 = 2 from nums2. Check cnt[2] = 0, so we found 0 pairs
• For nums1[3] = 3: We need 4 - 3 = 1 from nums2. Check cnt[1] = 0, so we found 0 pairs

Total: 3 + 3 + 0 + 0 = 6 pairs

Notice how the frequency counter allows us to instantly know how many times each value appears in nums2 without iterating through it. When we modify nums2, we only update the relevant counts in O(1) time, and counting pairs only requires iterating through the smaller nums1 array.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__: O(m) where m is the length of nums2, as we need to build a Counter from nums2
• add: O(1) for updating the counter and modifying the array element
• count: O(n) where n is the length of nums1, as we iterate through each element in nums1 and perform O(1) counter lookups

Overall, if count is called q times, the total time complexity for all count operations is O(n × q).

Space Complexity:

• The Counter self.cnt stores at most m unique values from nums2: O(m)
• We store references to nums1 and nums2: O(n + m)
• Overall space complexity: O(n + m), which simplifies to O(m) when considering the dominant term as mentioned in the reference (since we're primarily concerned with the additional space used by the data structure beyond the input arrays themselves)

The reference answer states O(n × q) for time complexity and O(m) for space complexity, where n and m are the lengths of nums1 and nums2 respectively, and q is the number of times the count method is called.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Update the Frequency Map Before Modifying the Array

A critical mistake is updating nums2[index] before adjusting the frequency map. This leads to incorrect frequency tracking.

Incorrect Implementation:

def add(self, index: int, val: int) -> None:
    # WRONG: Modifying array first loses the old value reference
    self.nums2[index] += val
    self.frequency_map[self.nums2[index]] += 1
    # The old value's count is never decremented!

Why it fails: Once you modify nums2[index], you lose track of what the old value was, making it impossible to decrement its count in the frequency map.

Correct Solution:

def add(self, index: int, val: int) -> None:
    # First: Decrement count of old value
    self.frequency_map[self.nums2[index]] -= 1
    # Second: Update the array
    self.nums2[index] += val
    # Third: Increment count of new value
    self.frequency_map[self.nums2[index]] += 1

2. Not Handling Negative Frequency Counts

When elements are removed from the frequency map (count becomes 0 or negative), not cleaning up can lead to memory inefficiency or logical errors in some implementations.

Potential Issue:

def add(self, index: int, val: int) -> None:
    self.frequency_map[self.nums2[index]] -= 1
    # If frequency becomes 0, the key still exists with value 0
    # This won't cause incorrect results but uses unnecessary memory

Optimized Solution:

def add(self, index: int, val: int) -> None:
    old_val = self.nums2[index]
    self.frequency_map[old_val] -= 1
    if self.frequency_map[old_val] == 0:
        del self.frequency_map[old_val]  # Clean up zero entries
    self.nums2[index] += val
    self.frequency_map[self.nums2[index]] += 1

3. Using Regular Dictionary Instead of Counter

Using a regular dictionary without proper initialization can cause KeyError when accessing non-existent keys.

Problematic Code:

def __init__(self, nums1: List[int], nums2: List[int]):
    self.frequency_map = {}  # Regular dict
    for num in nums2:
        self.frequency_map[num] = self.frequency_map.get(num, 0) + 1

def count(self, tot: int) -> int:
    # This will raise KeyError if (tot - x) doesn't exist in frequency_map
    return sum(self.frequency_map[tot - x] for x in self.nums1)

Solution: Use Counter (which returns 0 for missing keys) or handle missing keys explicitly:

def count(self, tot: int) -> int:
    return sum(self.frequency_map.get(tot - x, 0) for x in self.nums1)

4. Modifying nums1 Instead of nums2

The problem specifically states that only nums2 can be modified. Some might mistakenly try to optimize by choosing which array to modify based on size.

Wrong Assumption:

def __init__(self, nums1: List[int], nums2: List[int]):
    # WRONG: Trying to optimize by tracking the smaller array
    if len(nums1) < len(nums2):
        self.frequency_map = Counter(nums1)  # Wrong array!
        self.mutable = nums1  # Can't modify nums1!

Correct Approach: Always track nums2 in the frequency map since that's the only array that can be modified, regardless of relative sizes.