{x}
blog image

Finding Pairs With a Certain Sum

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.

 

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

 

Constraints:

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 105
  • 1 <= nums1[i] <= 109
  • 1 <= nums2[i] <= 105
  • 0 <= index < nums2.length
  • 1 <= val <= 105
  • 1 <= tot <= 109
  • At most 1000 calls are made to add and count each.

Solution Explanation: Finding Pairs With a Certain Sum

This problem requires designing a data structure to efficiently handle two types of queries: adding a value to an element in one array and counting pairs from two arrays that sum to a target value. A naive approach would have high time complexity. The optimal solution utilizes a hash table (or dictionary in Python) for efficient lookups and updates.

Approach:

  1. Initialization (__init__ or Constructor): The constructor initializes the data structure. It creates a hash table (cnt) to store the frequency of each element in nums2. This allows for O(1) lookup of element frequencies.

  2. Add Operation (add): The add method updates nums2 and the frequency count in cnt. It decrements the count of the old value and increments the count of the new value (after adding val). This maintains the accuracy of the frequency counts in cnt.

  3. Count Operation (count): The core of the solution lies in the count method. It iterates through nums1. For each element x in nums1, it checks the frequency of tot - x in cnt. The sum of these frequencies represents the number of pairs that sum to tot. This leverages the hash table for fast lookups, avoiding nested loops.

Time Complexity Analysis:

  • __init__ (Constructor): O(m), where m is the length of nums2, to initialize the hash table.
  • add: O(1) on average, as hash table operations (get, set) are typically O(1) on average. Worst-case is O(m) if all hash table elements collide (though unlikely).
  • count: O(n), where n is the length of nums1, to iterate through nums1. Each lookup in cnt is O(1) on average.

Therefore, the overall time complexity is dominated by the count operation, making it O(n) for each count call and O(m) for initialization. The add operation has an average time complexity of O(1).

Space Complexity Analysis:

The space complexity is O(m) because the hash table cnt stores the frequencies of elements in nums2, which, in the worst case, could store all unique elements of nums2.

Code Examples (Python, Java, C++, Go, TypeScript, JavaScript, C#):

The code examples in various languages provided in the previous response demonstrate the implementation details of this approach, accurately reflecting the described algorithm and data structure usage. Each code segment utilizes the hash table to achieve efficient time complexity for the count and add operations.