Vultr DocsLatest Content

Max Number of K-Sum Pairs

Updated on 11 June, 2025
Max Number of K-Sum Pairs header image

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

  • C++
  • Java
cpp 
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;
    }
};

The problem at hand requires finding the maximum number of pairs in a vector where the sum of each pair equals a given target value. The solution is implemented in C++ and employs an effective two-pointer approach.

  • Begin by sorting the vector to allow the two-pointer technique to work efficiently.
  • Establish two variables, start and end, at the beginning and end of the vector, respectively.
  • Incrementally check pairs:
    • If the sum of the values at start and end is less than the target, move the start pointer one step to the right to increase the sum.
    • If the sum is greater than the target, move the end pointer one step to the left to decrease the sum.
    • If the sum exactly matches the target, a valid pair is found. Increment both pointers towards the center and count the pair.
  • Continue the process until the start pointer meets or overtakes the end pointer, ensuring all possible pairs are checked.

This strategic use of pointers reduces the need for a nested loop, thus optimizing the performance significantly, especially for large lists. The final count of valid pairs is returned by the function. This approach effectively balances clarity and computational efficiency.

java 
class Solution {
    public int findPairs(int[] elements, int sum) {
        Arrays.sort(elements);
        int operations = 0;
        int i = 0;
        int j = elements.length - 1;
        while (i < j) {
            if (elements[i] + elements[j] < sum) {
                i++;
            } else if (elements[i] + elements[j] > sum) {
                j--;
            } else {
                i++;
                j--;
                operations++;
            }
        }
        return operations;
    }
}

In the provided Java solution, the goal is to count how many pairs of numbers in an array add up to a specific target sum. The process involves sorting the array first, and using a two-pointer technique to efficiently find and count the pairs.

  • Begin by sorting the array. This step ensures that traversal from both ends of the array will effectively find pairs that meet the sum condition.
  • Initialize two pointers, i starting at the beginning of the array and j starting at the end.
  • Implement a loop where i is always less than j. This loop will continue checking pairs without the two pointers crossing each other.
  • If the sum of the elements at the pointers i and j is less than the target, increment the i pointer to access a potentially larger value.
  • If their sum is greater than the target, decrement the j pointer to access a potentially smaller value.
  • If the elements at i and j exactly match the target sum, increment the operation count (representing a found pair), and move both pointers inward to continue the search.
  • Finally, return the count of operations, which represents the total number of pairs found that add up to the specified sum.

This solution leverages the sorted order of the array to minimize the needed comparisons and achieve efficient pair finding through adjusting the two boundaries pointed by i and j.

Comments

No comments yet.