Finding Pairs With a Certain Sum

Problem Statement

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 nums1.
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 and 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 numbers of pairs (i, j) such that nums1[i] + nums2[j] == tot.

LeetCode:

Finding Pairs With a Certain Sum

Constraints:

1 <= nums1.length <= 1000
1 <= nums2.length <= 10^5
1 <= nums1[i] <= 10^9
1 <= nums2[i] <= 10^5
0 <= index < nums2.length
1 <= val <= 10^5
1 <= tot <= 10^9
At most 1000 calls are made to add and count each.

Examples

Example 1:

Input: ["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]

Output: [null, 8, null, 2, 1, null, null, 11]

Explanation:
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);

findSumPairs.count(7);  // return 8; pairs (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) make 2 + 5 and pairs (5,1), (5,5) make 3 + 4

findSumPairs.add(3, 2); // now nums2 = [1,4,5,4,5,4]

findSumPairs.count(8);  // return 2; pairs (5,2), (5,4) make 3 + 5
findSumPairs.count(4);  // return 1; pair (5,0) makes 3 + 1
findSumPairs.add(0, 1); // now nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // now nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // return 11; pairs (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) make 2 + 5 and pairs (5,3), (5,5) make 3 + 4

Different Approaches

1️⃣ Brute Force Approach (Time Limit Exceeded)

Intuition:

For every count(tot), check all pairs (i, j) to see if nums1[i] + nums2[j] == tot.

Code:

class FindSumPairs {
    vector<int> nums1;
    vector<int> nums2;
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1 = nums1;
        this->nums2 = nums2;
    }
    
    void add(int index, int val) {
        nums2[index] += val;
    }
    
    int count(int tot) {
        int totalCount = 0;
        for(int i = 0; i < nums1.size(); i++) {
            for (int j = 0; j < nums2.size(); j++) {
                if (nums1[i] + nums2[j] == tot) {
                    totalCount++;
                }
            }
        }
        return totalCount;
    }
};

/**
 * 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);
 */

Complexity Analysis:

• Time Complexity:O(n*m)
  • where n is the number of element in nums1, while m is the number of elements in nums2.
• Space Complexity:O(1)

2️⃣ Optimal Approach

Intuition:

To efficiently count the number of pairs (i, j) such that nums1[i] + nums2[j] == tot, we use a hash map to store frequencies of elements from one of the arrays.

But which array should we store in the hash map?

Constraint Insight

According to the problem constraints:

• 1 ≤ nums1.length ≤ 1000
• 1 ≤ nums2.length ≤ 10⁵

If we store the frequency of elements from nums1, then during each count(tot) query, we would have to iterate through nums2 — which is large and costly.

Instead, we store the frequency of elements from nums2 in the hash map. This way, during a count(tot) query, we only need to iterate through nums1 (which is small), and for each nums1[i], compute:

target = tot - nums1[i];

We then look up target in the hashmap to find how many times it appears in nums2.

Benefit

• Time complexity of count() becomes O(n) where n = nums1.size(), which is efficient due to its small size.
• Updating the map during add() is O(1).

Code:

#include <vector>
#include <unordered_map>
using namespace std;

// Class to perform operations on two arrays to find pairs with a certain sum
class FindSumPairs {
private:
    vector<int> nums1;                  // First input array (size is small, max 1000)
    vector<int> nums2;                  // Second input array (can be large, up to 10^5)
    unordered_map<int, int> freq2;      // Hash map to store the frequency of each number in nums2

public:
    // Constructor: initializes the object with nums1 and nums2
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        this->nums1 = nums1;            // Store nums1
        this->nums2 = nums2;            // Store nums2

        // Build the frequency map for nums2
        for (int num : nums2) {
            freq2[num]++;               // Count how many times each number appears in nums2
        }
    }

    // Adds 'val' to nums2[index]
    void add(int index, int val) {
        int old_val = nums2[index];     // Get the old value at the index
        freq2[old_val]--;               // Decrease its count in the frequency map

        nums2[index] += val;            // Update the value at the index

        freq2[nums2[index]]++;          // Increase the count of the new value in the map
    }

    // Returns the number of valid (i, j) pairs such that nums1[i] + nums2[j] == tot
    int count(int tot) {
        int totalCount = 0;             // Initialize total pair count

        // Loop through all elements in nums1
        for (int num : nums1) {
            int target = tot - num;     // We need nums2[j] to be equal to 'target' to make the sum == tot

            // Check if 'target' exists in nums2 using the frequency map
            if (freq2.count(target)) {
                totalCount += freq2[target];  // Add the number of times 'target' appears in nums2
            }
        }

        return totalCount;              // Return total valid pairs
    }
};

Complexity Analysis:

• Time Complexity:O(n)
  • Where n is the size of the nums1 array
• Space Complexity:O(m)
  • unordered_map of size m for the nums2.