LeetCode //C - 1679. Max Number of K-Sum Pairs

1679. Max Number of K-Sum Pairs

You are given an integer array nums and an integer k.

In one operation, you can pick two numbers from the array whose sum equals k and remove them from the array.

Return the maximum number of operations you can perform on the array.
?

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<=10^5$
• $1<=nums[i]<=10^9$
• $1<=k<=10^9$

From: LeetCode
Link: 1679. Max Number of K-Sum Pairs

Solution:

Ideas：

1. Sort the Array: We sort the array to arrange the numbers in ascending order. This helps in efficiently finding pairs with a sum equal to k.

2. Use Two Pointers: Initialize two pointers, one at the start (left) and one at the end (right) of the array. If the sum of the elements at these two pointers is equal to k, we found a valid pair, so we increment our count and move both pointers (increment left and decrement right). If the sum is less than k, we move the left pointer to the right (increment left) to increase the sum. If the sum is more than k, we move the right pointer to the left (decrement right) to decrease the sum.

3. Repeat Until Pointers Meet: Continue the process until the left pointer is not less than the right pointer.

4. Return the Count: The count of operations performed (pairs found) is the answer.

Code:

int compare(const void *a, const void *b) {
    return *(int*)a - *(int*)b;
}

int maxOperations(int* nums, int numsSize, int k) {
    qsort(nums, numsSize, sizeof(int), compare); // Sort the array
    int left = 0, right = numsSize - 1;
    int count = 0;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == k) {
            count++;  // Found a valid pair
            left++;   // Move left pointer to the right
            right--;  // Move right pointer to the left
        } else if (sum < k) {
            left++;   // Increase the sum
        } else {
            right--;  // Decrease the sum
        }
    }

    return count;
}