Max Number of K-Sum Pairs

Medium
761.

Max Number of K-Sum Pairs

Max Number of K-Sum Pairs is a medium coding problem on arrays, hash table and sorting, asked in Amazon, Google and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxOperations = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Max Number of K-Sum Pairs — Solution in Python, Java & C++

Max Number of K-Sum Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Max Number of K-Sum Pairs is a medium coding problem on arrays, hash table and sorting, asked in Amazon, Google and Flipkart interviews.

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

Hints for Max Number of K-Sum Pairs

  1. Hint 1

    Sort, then walk two pointers inward — this pairs each element with its only viable partner.

  2. Hint 2

    On a match, consume both and move both pointers.

  3. Hint 3

    A hash-map count works too: for each value pair it with k - value while both counts last.

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

  1. Sort a copy of nums.
  2. Set lo at the front, hi at the back.
  3. On s[lo] + s[hi] == k, count an operation and move both pointers inward.
  4. 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

Java

public static int maxOperations(int[] nums, int k) {
    int[] s = nums.clone();
    Arrays.sort(s);
    int lo = 0, hi = s.length - 1, count = 0;
    while (lo < hi) {
        long sum = (long) s[lo] + s[hi];
        if (sum == k) { count++; lo++; hi--; }
        else if (sum < k) lo++;
        else hi--;
    }
    return count;
}

C++

int maxOperations(vector<int>& nums, int k) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    int lo = 0, hi = (int) s.size() - 1, count = 0;
    while (lo < hi) {
        long long sum = (long long) s[lo] + s[hi];
        if (sum == k) { count++; lo++; hi--; }
        else if (sum < k) lo++;
        else hi--;
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets