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.
- 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 <= 1000001 <= nums[i] <= 10000000001 <= k <= 1000000000
Hints for Max Number of K-Sum Pairs
Hint 1
Sort, then walk two pointers inward — this pairs each element with its only viable partner.
Hint 2
On a match, consume both and move both pointers.
Hint 3
A hash-map count works too: for each value pair it with
k - valuewhile 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
- Sort a copy of
nums. - Set
loat the front,hiat the back. - On
s[lo] + s[hi] == k, count an operation and move both pointers inward. - Otherwise move
loup (sum too small) orhidown (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 == kmust 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 countJava
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