Max Number of K-Sum Pairs — Medium Problem & Solution

One operation removes two elements whose sum is exactly k. Return the maximum number of operations you can perform.

Difficulty: Medium
Topics: Arrays, Hash Table, Sorting, Two Pointers
Asked at: Amazon, Google, Flipkart
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

One operation removes two elements whose sum is exactly k.

Return the maximum number of operations you can perform.

Example 1

Input: nums = [1,2,3,4], k = 5
Output: 2
Explanation: Remove 1 and 4, then 2 and 3.

Example 2

Input: nums = [3,1,3,4,3], k = 6
Output: 1
Explanation: Only one pair of 3s can be removed.

Example 3

Input: nums = [2,2,2,2], k = 4
Output: 2

Constraints

1 <= nums.length <= 100000
1 <= nums[i] <= 1000000000
1 <= k <= 1000000000

How to solve Max Number of K-Sum Pairs

Sorting turns the pairing into a two-pointer sweep: a sum that is too small can only be fixed by raising the left value, and a sum that is too large by lowering the right one.

Approach

Sort a copy of nums.
Set lo at the front, hi at the back.
On s[lo] + s[hi] == k, count an operation and move both pointers inward.
Otherwise move lo up (sum too small) or hi down (sum too big).

Why it works

Each element has exactly one partner value, k - x. The sweep pairs the smallest available element with the largest that can still work, and discarding an element only happens when no remaining partner exists for it — so the count is maximal.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Moving only one pointer after a successful pair reuses an element.
With a hash map, 2 * x == k must be handled by pairing within the same bucket, halving the count.
Elements are consumed, so a greedy that re-scans without removal overcounts.

Reference solution

Python

from typing import List

def maxOperations(nums: List[int], k: int) -> int:
    s = sorted(nums)
    lo, hi, count = 0, len(s) - 1, 0
    while lo < hi:
        total = s[lo] + s[hi]
        if total == k:
            count += 1
            lo += 1
            hi -= 1
        elif total < k:
            lo += 1
        else:
            hi -= 1
    return count

JavaScript

var maxOperations = function(nums, k) {
    var s = nums.slice().sort(function(a, b) { return a - b; });
    var lo = 0, hi = s.length - 1, count = 0;
    while (lo < hi) {
        var sum = s[lo] + s[hi];
        if (sum === k) { count++; lo++; hi--; }
        else if (sum < k) lo++;
        else hi--;
    }
    return count;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue