1679. Max Number of K-Sum Pairs Medium

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.

Approach

Input: An integer array nums and an integer k

Output: Every operation picks two numbers summing to k. Return the maximum number of operations possible.

This problem uses a Two Pointers (Sliding Window variation) technique, though since it relies heavily on sorting first, it's primarily a Two Pointer problem.

We first sort the array, then build a two-pointer window from both ends.

• If the sum of the left and right values is < k, we move the left pointer rightward (to increase the sum)
• If the sum of the left and right values is > k, we move the right pointer leftward (to decrease the sum)
• If the sum of the left and right values is == k, we record an operation and move both pointers inwards

Finally, return the operation count.

Implementation

python

class Solution:
    def maxOperations(self, nums: List[int], k: int) -> int:
        # Sort the array `nums`
        nums.sort()

        # Initialize two pointers, `l` points to start, `r` points to the end
        l, r = 0, len(nums) - 1

        # Track the number of valid pairs
        ans = 0

        # Loop as long as left pointer is strictly less than right pointer
        while l < r:
            # If the sum of the two current numbers is greater than the target `k`
            if nums[l] + nums[r] > k:
                # Move the right pointer to the left to try to decrease the sum
                r -= 1
            # If the sum of the two current numbers is less than the target `k`
            elif nums[l] + nums[r] < k:
                # Move the left pointer to the right to try to increase the sum
                l += 1
            else:
                # If the current sum exactly matches the target `k`
                ans += 1  # Record one valid pair operation
                l += 1    # Move the left pointer forward
                r -= 1    # Move the right pointer backward
        
        # Return the number of established pairs recorded
        return ans

javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxOperations = function(nums, k) {
    nums.sort((a, b) => a - b);

    let l = 0;
    let r = nums.length - 1;
    let ans = 0;

    while (l < r) {
        if (nums[l] + nums[r] < k) {
            l++;
        } else if (nums[l] + nums[r] > k) {
            r--;
        } else {
            ans++;
            l++;
            r--;
        }
    }

    return ans;
};

Complexity Analysis

• Time Complexity: O(n log n) due to sorting, traversing is O(n)
• Space Complexity: O(1) or O(log n) depending on language sorting algorithms

Links

1679. Max Number of K-Sum Pairs (English)1679. K 和数对的最大数目 (Chinese)