Max Number of K-Sum Pairs

Problem Statement

In this task, you have an integer array nums and a specific integer k. You can perform an operation where two numbers from this array, which together add up to k, are removed. The goal is to calculate and return the maximum number of such operations that can be performed using the elements in the array. Each operation should find and remove a unique pair that sums up to k.

Examples

Example 1

Input:

nums = [1,2,3,4], k = 5

Output:

2

Explanation:

Starting with nums = [1,2,3,4]:
- Remove numbers 1 and 4, then nums = [2,3]
- Remove numbers 2 and 3, then nums = []
There are no more pairs that sum up to 5, hence a total of 2 operations.

Example 2

Input:

nums = [3,1,3,4,3], k = 6

Output:

1

Explanation:

Starting with nums = [3,1,3,4,3]:
- Remove the first two 3's, then nums = [1,4,3]
There are no more pairs that sum up to 6, hence a total of 1 operation.

Constraints

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109

Approach and Intuition

Given the nature of the problem, our primary aim is to efficiently find pairs that sum up to k, and then to maximize the number of such pairs we can remove from the array. Here's a strategic breakdown on how this could be achieved:

1. Use of Hashing: Utilizing a hashmap can be pivotal. For every element in the array, the complement to k can be calculated (i.e., k - currentElement). Using a hashmap helps in checking if this complement exists in the array in constant time.

2. Iterative Checking: As we move through each element:

   • If its complement (as required to sum to k) exists in our hashmap, it means a pair can be formed, so we increase our count of operations and adjust the frequency of the numbers in the hashmap.
   • If not, increase the frequency of this number in our hashmap.

3. Considering Frequencies: Since the same number might appear multiple times in the array, managing the frequency of each number becomes key. Each time a valid pair is found, the frequency of the involved numbers must be decremented. If a frequency falls to zero, it should no longer be considered available for pairing.

4. Edge Cases: Handle scenarios where the array size is minimal or the k value is less than any possible combination in nums.

Through this iterative and hashmap-based approach, not only can we efficiently check for and count pairs, but also manage multiple occurrences, thereby deriving the maximum number of operations possible as outlined in the provided examples.

Solutions

class Solution {
public:
    int findMaxPairs(vector<int>& elements, int target) {
        sort(elements.begin(), elements.end());
        int pairs = 0;
        int start = 0;
        int end = elements.size() - 1;
        while (start < end) {
            if (elements[start] + elements[end] < target) {
                start++;
            } else if (elements[start] + elements[end] > target) {
                end--;
            } else {
                start++;
                end--;
                pairs++;
            }
        }
        return pairs;
    }
};