Code Implementation

class FindSumPairs:
    def __init__(self, nums1: List[int], nums2: List[int]):
        from collections import Counter
        self.nums1 = nums1
        self.nums2 = nums2
        self.nums2_count = Counter(nums2)

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

    def count(self, tot: int) -> int:
        ans = 0
        for a in self.nums1:
            b = tot - a
            ans += self.nums2_count.get(b, 0)
        return ans
      

class FindSumPairs {
    vector<int> nums1, nums2;
    unordered_map<int, int> nums2_count;
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1 = nums1;
        this->nums2 = nums2;
        for (int n : nums2) ++nums2_count[n];
    }

    void add(int index, int val) {
        int old_val = nums2[index];
        --nums2_count[old_val];
        if (nums2_count[old_val] == 0) nums2_count.erase(old_val);
        nums2[index] += val;
        ++nums2_count[nums2[index]];
    }

    int count(int tot) {
        int result = 0;
        for (int a : nums1) {
            int b = tot - a;
            if (nums2_count.count(b))
                result += nums2_count[b];
        }
        return result;
    }
};
      

class FindSumPairs {
    private int[] nums1, nums2;
    private Map<Integer, Integer> nums2Count;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        nums2Count = new HashMap<>();
        for (int n : nums2) {
            nums2Count.put(n, nums2Count.getOrDefault(n, 0) + 1);
        }
    }

    public void add(int index, int val) {
        int oldVal = nums2[index];
        nums2Count.put(oldVal, nums2Count.get(oldVal) - 1);
        if (nums2Count.get(oldVal) == 0) nums2Count.remove(oldVal);
        nums2[index] += val;
        int newVal = nums2[index];
        nums2Count.put(newVal, nums2Count.getOrDefault(newVal, 0) + 1);
    }

    public int count(int tot) {
        int res = 0;
        for (int a : nums1) {
            int b = tot - a;
            res += nums2Count.getOrDefault(b, 0);
        }
        return res;
    }
}
      

var FindSumPairs = function(nums1, nums2) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    this.nums2Count = new Map();
    for (let n of nums2) {
        this.nums2Count.set(n, (this.nums2Count.get(n) || 0) + 1);
    }
};

FindSumPairs.prototype.add = function(index, val) {
    let oldVal = this.nums2[index];
    this.nums2Count.set(oldVal, this.nums2Count.get(oldVal) - 1);
    if (this.nums2Count.get(oldVal) === 0) this.nums2Count.delete(oldVal);
    this.nums2[index] += val;
    let newVal = this.nums2[index];
    this.nums2Count.set(newVal, (this.nums2Count.get(newVal) || 0) + 1);
};

FindSumPairs.prototype.count = function(tot) {
    let res = 0;
    for (let a of this.nums1) {
        let b = tot - a;
        res += this.nums2Count.get(b) || 0;
    }
    return res;
};
      

Problem Description

You are given two integer arrays, nums1 and nums2. You need to design a class that supports two operations:

• add(index, val): Add val to the element at position index in nums2.
• count(tot): Return the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Each pair uses one element from nums1 and one from nums2. Elements may be reused across different queries, but within a single pair, each index is used once. The arrays can be large, and there may be many queries, so efficiency is important.

Thought Process

At first glance, it seems straightforward: for each count query, simply check every possible pair of elements from nums1 and nums2 to see if they sum to tot. But this brute-force approach is inefficient, especially if the arrays are large or there are many queries.

To optimize, we notice that nums1 does not change, but nums2 can be updated. For each count query, if we can quickly find how many numbers in nums2 match a needed value for each nums1[i], we can avoid checking every pair explicitly. Using a hash map to store counts of numbers in nums2 allows us to do this efficiently.

Solution Approach

• Initialization: Store nums1 and nums2. Build a hash map (dictionary) to count occurrences of each number in nums2.
• add(index, val):
  • Update the count of the old value at nums2[index] in the hash map (decrement or remove if zero).
  • Add val to nums2[index].
  • Update the count of the new value in the hash map (increment or add).
• count(tot):
  • For each number a in nums1, compute b = tot - a.
  • Look up b in the hash map for nums2; the value gives how many times nums2[j] can pair with a to make tot.
  • Sum these counts for all a in nums1.

This approach ensures that add and count operations are efficient, using the hash map for quick lookups and updates.

Example Walkthrough

Suppose nums1 = [1, 2, 3] and nums2 = [3, 4].

Initial hash map for nums2: {3: 1, 4: 1}

count(6):

• For a = 1, need 6 - 1 = 5; nums2 has 0.
• For a = 2, need 6 - 2 = 4; nums2 has 1.
• For a = 3, need 6 - 3 = 3; nums2 has 1.
• Total pairs: 1 (from 2+4) + 1 (from 3+3) = 2.

add(0, 1):

• nums2[0] becomes 4 (was 3), so hash map updates: {3: 0, 4: 2}.

count(6):

• For a = 1, need 5; count is 0.
• For a = 2, need 4; count is 2.
• For a = 3, need 3; count is 0.
• Total pairs: 2 (from 2+4 and 2+4 again) = 2.

Time and Space Complexity

• Brute-force Approach:
  • count(tot): O(N * M), where N and M are the lengths of nums1 and nums2.
  • add(index, val): O(1).
• Optimized Approach:
  • count(tot): O(N), since we loop through nums1 and do a hash map lookup for each.
  • add(index, val): O(1), because updating the hash map is constant time.
  • Space: O(M) for the hash map storing counts of nums2 values.

The optimized solution is much more efficient for large arrays and many queries.

Summary

By using a hash map to track the counts of numbers in nums2, we can efficiently answer count queries by simply looking up the needed complement for each value in nums1. This avoids the need to check every possible pair explicitly. Updates to nums2 are handled by adjusting the counts in the hash map. The result is a fast and elegant solution that handles both operations efficiently, making it well-suited for large inputs or frequent queries.