Finding Pairs With a Certain Sum

The first solution I thought of occured when I saw the restraints for nums1 and nums2.

After seeing that 1 <= nums1.length <= 1000 and 1 <= nums2.length <= 10^5, there must exist a solution which revolved around placing all nums2 elements into a hashmap, then iterating through nums1 (since it is wayyyyy smaller) to see how many of the corresponding number in nums2 exists.

Therefore,

for the add operation, we simply just update nums2 and the hashmap

for the count operation, we iterate through nums1 and calculate the difference between tot and nums1[i]. Then, just sum together the number of occurences of the difference in nums2.

code

class FindSumPairs {
public:
    vector<int> arr1;
    vector<int> arr2;
    unordered_map<int, int> mp;
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        arr1 = nums1;
        arr2 = nums2;
        for (int& num : arr2) {
            ++mp[num];
        }
    }

    void add(int index, int val) {
        --mp[arr2[index]];
        arr2[index] += val;
        ++mp[arr2[index]];
    }

    int count(int tot) {
        int ans = 0;
        for (int& num : arr1) {
            int difference = tot-num;
            if (mp.count(difference)) {
                ans += mp[difference];
            }
        }
        return ans;
    }
};

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs* obj = new FindSumPairs(arr1, arr2);
 * obj->add(index,val);
 * int param_2 = obj->count(tot);
 */

complexity

Time: O(n + m + q_1 + q_2 * n) where:

n is the size of nums1

m is the size of nums2

q_1 is the number of add queries

q_2 is the number of count queries

Space: O(n + m)

learnings

if (mp.count(difference)) {
    ans += mp[difference];
}

adding the mp.count(difference) to check for difference makes it faster:

otherwise, with ans += mp[difference] you end up inserting difference into mp if it does not exist, modifying the hashmap and adding unnecessary key value pairs

time taken

11 minutes and 58 seconds