# Finding Pairs With a Certain Sum
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/finding-pairs-with-a-certain-sum)
Canonical: https://scaleengineer.com/dsa/problems/finding-pairs-with-a-certain-sum
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Data structures:** Array, Hash Table
**Companies:** [Databricks](https://scaleengineer.com/companies/databricks), [Quora](https://scaleengineer.com/companies/quora)
---
## 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`.

**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**.

# Approaches
## Brute Force Iteration
This is the most straightforward approach where we directly translate the problem statement into code. We keep the original arrays and, for each `count` query, we iterate through all possible pairs from `nums1` and `nums2` to see how many of them sum up to the target value `tot`.
**Time:** - **Constructor**: O(1) (or O(L1 + L2) if copying arrays).
- **`add`**: O(1).
- **`count`**: O(L1 * L2), where L1 and L2 are the lengths of `nums1` and `nums2` respectively. This is the bottleneck. · **Space:** O(1), as we only store references to the input arrays. If we make copies, it would be O(L1 + L2).
**Pros:** Very simple to understand and implement.; The `add` operation is extremely fast, taking constant time.; Requires minimal extra space.
**Cons:** The `count` operation is extremely slow, with a time complexity of O(L1 * L2). Given the problem constraints (L1 up to 1000, L2 up to 10^5), this will result in a 'Time Limit Exceeded' error on most platforms.
### Explanation
In this approach, the `FindSumPairs` class holds the two arrays. The `add` operation is very simple and efficient, as it only involves updating an element in `nums2` at a specific index. The main drawback is the `count` method. It employs a nested loop structure: the outer loop goes through each element of `nums1`, and for each of these, the inner loop goes through every element of `nums2`. This exhaustive check of all pairs makes the `count` operation computationally expensive, especially with the given constraints where `nums2` can be very large.

```java
class FindSumPairs {
    private int[] nums1;
    private int[] nums2;

    public FindSumPairs(int[] nums1, int[] nums2) {
        this.nums1 = nums1;
        this.nums2 = nums2;
    }

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

    public int count(int tot) {
        int pairCount = 0;
        for (int num1 : nums1) {
            for (int num2 : nums2) {
                if (num1 + num2 == tot) {
                    pairCount++;
                }
            }
        }
        return pairCount;
    }
}
```
### Algorithm
- **Constructor `FindSumPairs(nums1, nums2)`**: Store references to the input arrays `nums1` and `nums2`.
- **`add(index, val)`**: Directly update the value in the `nums2` array at the given index: `nums2[index] += val`.
- **`count(tot)`**: 
  1. Initialize a counter `pairCount` to 0.
  2. Use nested loops to iterate through every possible pair of elements `(nums1[i], nums2[j])`.
  3. For each pair, check if their sum equals `tot`.
  4. If `nums1[i] + nums2[j] == tot`, increment `pairCount`.
  5. After checking all pairs, return `pairCount`.

## Optimized Counting with a Hash Map
This optimized approach addresses the inefficiency of the brute-force `count` method. By using a hash map to store the frequencies of numbers in the larger array, `nums2`, we can significantly speed up the process of finding pairs. The key insight is that for any `num1` from `nums1`, we need to find how many elements in `nums2` are equal to `tot - num1`. A frequency map allows us to answer this query in constant time on average.
**Time:** - **Constructor**: O(L2) to build the frequency map.
- **`add`**: O(1) on average due to hash map operations.
- **`count`**: O(L1) because we iterate through `nums1` and perform an O(1) lookup for each element. · **Space:** O(L2), for storing the frequency map of `nums2`. In the worst case, if all elements in `nums2` are unique, the map will have L2 entries.
**Pros:** The `count` operation is significantly faster, with a time complexity of O(L1), making it highly efficient for the given constraints.; The `add` operation remains fast, taking O(1) average time.; This approach is well-balanced for the problem's specific constraints and call patterns.
**Cons:** Requires additional space to store the frequency map for `nums2`, which can be up to O(L2) in the worst case.; The `add` operation is slightly more complex as it needs to maintain the state of the frequency map.
### Explanation
We pre-process `nums2` in the constructor by building a hash map that maps each unique number to its count. This allows the `count(tot)` operation to be much faster. Instead of a nested loop, we only need to loop through the smaller array, `nums1`. For each `num1`, we calculate the `complement` needed to reach `tot` and then perform a quick O(1) average time lookup in our hash map to find how many such complements exist in `nums2`.

The `add(index, val)` operation needs to be updated to keep the frequency map consistent. When a value in `nums2` is changed, we must decrement the count of the old value and increment the count of the new value in the map. Given that `nums1` is much smaller than `nums2` and `count` is called frequently, this trade-off is highly beneficial.

```java
import java.util.HashMap;
import java.util.Map;

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

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

    public void add(int index, int val) {
        int oldVal = nums2[index];
        // Decrease the frequency of the old value
        freq2.put(oldVal, freq2.get(oldVal) - 1);
        if (freq2.get(oldVal) == 0) {
            freq2.remove(oldVal);
        }

        int newVal = oldVal + val;
        nums2[index] = newVal;
        // Increase the frequency of the new value
        freq2.put(newVal, freq2.getOrDefault(newVal, 0) + 1);
    }

    public int count(int tot) {
        int totalPairs = 0;
        for (int num1 : nums1) {
            int complement = tot - num1;
            totalPairs += freq2.getOrDefault(complement, 0);
        }
        return totalPairs;
    }
}
```
### Algorithm
- **Constructor `FindSumPairs(nums1, nums2)`**:
  1. Store `nums1` and `nums2`.
  2. Create a hash map, `freqMap`, to store the frequency of each number in `nums2`.
  3. Iterate through `nums2` and populate `freqMap`.
- **`add(index, val)`**:
  1. Get the old value `oldVal = nums2[index]`.
  2. Decrement the frequency of `oldVal` in `freqMap`.
  3. Update the array: `nums2[index] += val`.
  4. Get the new value `newVal = nums2[index]`.
  5. Increment the frequency of `newVal` in `freqMap`.
- **`count(tot)`**:
  1. Initialize `pairCount = 0`.
  2. Iterate through each number `num1` in `nums1`.
  3. Calculate the required complement: `complement = tot - num1`.
  4. Look up the frequency of `complement` in `freqMap` and add it to `pairCount`.
  5. Return `pairCount`.

# Solutions
### CSharp

```csharp
public class FindSumPairs { private int [] nums1 ; private int [] nums2 ; private Dictionary < int , int > cnt = new Dictionary < int , int >(); public FindSumPairs ( int [] nums1 , int [] nums2 ) { this . nums1 = nums1 ; this . nums2 = nums2 ; foreach ( int x in nums2 ) { if ( cnt . ContainsKey ( x )) { cnt [ x ]++; } else { cnt [ x ] = 1 ; } } } public void Add ( int index , int val ) { int oldVal = nums2 [ index ]; if ( cnt . TryGetValue ( oldVal , out int oldCount )) { if ( oldCount == 1 ) { cnt . Remove ( oldVal ); } else { cnt [ oldVal ] = oldCount - 1 ; } } nums2 [ index ] += val ; int newVal = nums2 [ index ]; if ( cnt . TryGetValue ( newVal , out int newCount )) { cnt [ newVal ] = newCount + 1 ; } else { cnt [ newVal ] = 1 ; } } public int Count ( int tot ) { int ans = 0 ; foreach ( int x in nums1 ) { int target = tot - x ; if ( cnt . TryGetValue ( target , out int count )) { ans += count ; } } return ans ; } } /** * 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); */
```

### Java

```java
class FindSumPairs { private int [] nums1 ; private int [] nums2 ; private Map < Integer , Integer > cnt = new HashMap <>(); public FindSumPairs ( int [] nums1 , int [] nums2 ) { this . nums1 = nums1 ; this . nums2 = nums2 ; for ( int v : nums2 ) { cnt . put ( v , cnt . getOrDefault ( v , 0 ) + 1 ); } } public void add ( int index , int val ) { int old = nums2 [ index ]; cnt . put ( old , cnt . get ( old ) - 1 ); cnt . put ( old + val , cnt . getOrDefault ( old + val , 0 ) + 1 ); nums2 [ index ] += val ; } public int count ( int tot ) { int ans = 0 ; for ( int v : nums1 ) { ans += cnt . getOrDefault ( tot - v , 0 ); } return ans ; } } /** * 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); */
```

### JavaScript

```javascript
/** * @param {number[]} nums1 * @param {number[]} nums2 */ var FindSumPairs =
  function (nums1, nums2) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    this.cnt = new Map();
    for (const x of nums2) {
      this.cnt.set(x, (this.cnt.get(x) || 0) + 1);
    }
  };
/** * @param {number} index * @param {number} val * @return {void} */ FindSumPairs.prototype.add =
  function (index, val) {
    const old = this.nums2[index];
    this.cnt.set(old, this.cnt.get(old) - 1);
    this.nums2[index] += val;
    const now = this.nums2[index];
    this.cnt.set(now, (this.cnt.get(now) || 0) + 1);
  };
/** * @param {number} tot * @return {number} */ FindSumPairs.prototype.count =
  function (tot) {
    return this.nums1.reduce((acc, x) => acc + (this.cnt.get(tot - x) || 0), 0);
  }; /** * Your FindSumPairs object will be instantiated and called as such: * var obj = new FindSumPairs(nums1, nums2) * obj.add(index,val) * var param_2 = obj.count(tot) */

```

### Python

```python
class FindSumPairs : def __init__ ( self , nums1 : List [ int ], nums2 : List [ int ]): self . nums1 = nums1 self . nums2 = nums2 self . cnt = Counter ( nums2 ) def add ( self , index : int , val : int ) -> None : old = self . nums2 [ index ] self . cnt [ old ] -= 1 self . cnt [ old + val ] += 1 self . nums2 [ index ] += val def count ( self , tot : int ) -> int : return sum ( self . cnt [ tot - v ] for v in self . nums1 ) # Your FindSumPairs object will be instantiated and called as such: # obj = FindSumPairs(nums1, nums2) # obj.add(index,val) # param_2 = obj.count(tot)
```

### CPP

```cpp
class FindSumPairs { public: FindSumPairs ( vector < int >& nums1 , vector < int >& nums2 ) { this -> nums1 = nums1 ; this -> nums2 = nums2 ; for ( int & v : nums2 ) { ++ cnt [ v ]; } } void add ( int index , int val ) { int old = nums2 [ index ]; -- cnt [ old ]; ++ cnt [ old + val ]; nums2 [ index ] += val ; } int count ( int tot ) { int ans = 0 ; for ( int & v : nums1 ) { ans += cnt [ tot - v ]; } return ans ; } private: vector < int > nums1 ; vector < int > nums2 ; unordered_map < int , int > cnt ; }; /** * 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); */
```