Leetcode 1865 - Finding Pairs With a Certain Sum

Link to problem

Problem

You are given two integer arrays nums1 and nums2. You are tasked to implement a data structure that supports queries of two types:

1. Add a positive integer to an element of a given index in the array nums2.
2. Count the number of pairs (i, j) such that nums1[i] + nums2[j] equals a given value (0 <= i < nums1.length and 0 <= j < nums2.length).

Implement the FindSumPairs class:

• FindSumPairs(int[] nums1, int[] nums2) Initializes the FindSumPairs object with two integer arrays nums1 and nums2.
• void add(int index, int val) Adds val to nums2[index], i.e., apply nums2[index] += val.
• int count(int tot) Returns the number of pairs (i, j) such that nums1[i] + nums2[j] == tot.

Solution

Very similar to the twoSum problem. Only that we need to update nums2 and the hash map for nums2 that stores the frequency of numbers in nums2.

For method count, we only need to check if the differnce number exist in nums2 from substracting target number by numbers in nums1. Afterwards, we could get the number of possible pairs simply by multiplying the frequency of the numbers in both arrays.

Implementation

class FindSumPairs {
private:
    unordered_map<int, int> nums1Count, nums2Count;
    vector<int> nums2;

public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2): nums2(nums2) {
        for (auto i: nums1) nums1Count[i]++;
        for (auto i: nums2) nums2Count[i]++;
    }

    void add(int index, int val) {
        int temp = nums2[index];
        nums2[index] += val;
        nums2Count[temp]--;
        nums2Count[nums2[index]]++;
    }

    int count(int tot) {
        int sum = 0;
        for(const auto& p: nums1Count) {
            int diff = tot - p.first;
            sum += p.second * nums2Count[diff];
        }
        return sum;
    }

};

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