Max Number of K-Sum Pairs

medium array two pointers hash map

Problem

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.

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

Output1

Sorted: [1,3,3,3,4]. Pair (3, 3) sums to 6; only one such disjoint pair.

nums (comma-separated)

def max_operations(nums, k):
    nums.sort()
    l, r = 0, len(nums) - 1
    count = 0
    while l < r:
        s = nums[l] + nums[r]
        if s == k:
            count += 1; l += 1; r -= 1
        elif s < k: l += 1
        else: r -= 1
    return count

function maxOperations(nums, k) {
  nums.sort((a, b) => a - b);
  let l = 0, r = nums.length - 1, count = 0;
  while (l < r) {
    const s = nums[l] + nums[r];
    if (s === k) { count++; l++; r--; }
    else if (s < k) l++;
    else r--;
  }
  return count;
}

class Solution {
    public int maxOperations(int[] nums, int k) {
        Arrays.sort(nums);
        int l = 0, r = nums.length - 1, count = 0;
        while (l < r) {
            int s = nums[l] + nums[r];
            if (s == k) { count++; l++; r--; }
            else if (s < k) l++;
            else r--;
        }
        return count;
    }
}

int maxOperations(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());
    int l = 0, r = (int)nums.size() - 1, count = 0;
    while (l < r) {
        int s = nums[l] + nums[r];
        if (s == k) { count++; l++; r--; }
        else if (s < k) l++;
        else r--;
    }
    return count;
}

Explanation

We want to pair up numbers that add to k and count how many such disjoint pairs we can form. The trick is to sort the array first, then squeeze inward with two pointers from both ends.

Put l at the smallest value and r at the largest, and look at their sum s = nums[l] + nums[r]. If the sum is exactly k, we found a pair: increment count and move both pointers inward.

If the sum is too small, the only way to grow it is to raise the low end, so move l right. If it is too big, lower the high end by moving r left. Sorting is what makes these moves correct — it guarantees the sum changes in the direction we expect.

Example: nums = [3,1,3,4,3], k = 6. Sorted it is [1,3,3,3,4]. 1+4=5 is too small so move l; 3+4=7 is too big so move r; 3+3=6 matches, count becomes 1. The pointers then cross, so the answer is 1.

The sort dominates the cost at O(n log n), while the pointer sweep itself is a single linear pass.

Time: O(n log n) Space: O(1) beyond the sort