Max Number of K-Sum Pairs
Max Number of K-Sum Pairs: repeatedly remove two numbers summing to k and return the maximum number of such operations you can perform.
- 1 <= nums.length <= 10⁵
- 1 <= nums[i] <= 10⁹
- 1 <= k <= 10⁹
Intuition
Every number needs a partner of value k - num. Walk once with a map of unmatched values: if the partner is waiting, consume it and score a pair; otherwise park the current number to wait for its own partner. Nothing needs sorting, and greed is safe because all pairs are worth exactly one.
'Find pairs summing to a target' is the Two Sum family, and the counting-map variant appears whenever elements can be consumed. The tell here is repeatedly remove — meaning disjoint pairs — which rules out reusing an element and makes a count map, not a plain set, the right structure.
Approach
Before reading on: since every operation scores exactly 1, does it ever matter which pair you form first? Then decide what you must remember about numbers that have not yet found a partner. Aim for O(n).
Every pair is worth the same, so order does not matter
Because each operation scores exactly 1, there is no reason to prefer one pair over another — the goal is simply to form as many disjoint pairs as possible. That removes any need to search or backtrack. The only real constraint is that each number can be used once, so the bookkeeping is about consumption, not choice.
Hash map of unmatched values
Keep a map from value to how many copies are still waiting for a partner. For each num, look up k - num. If its count is positive, one waiting copy pairs off: decrement that count and increment the answer. Otherwise num has no partner yet, so increment its own count and let it wait. One pass, O(n) time and O(n) space, and it never needs the array sorted.
The two-pointer alternative
Sorting first allows a pointer at each end: if the two sum above k move the right pointer in, if below move the left out, and if equal count a pair and move both. That is O(n log n) time but O(1) extra space beyond the sort. Choose the hash map when time matters and the two-pointer walk when memory does — both are standard answers, and naming the trade-off is usually the point of the follow-up.
Solution & live demo
Common pitfalls
Using a set instead of a count map
if partner in seen:
seen.remove(partner)if waiting[partner] > 0:
waiting[partner] -= 1A set cannot represent two copies of the same value. On [3,3,3,3] with k=6 it forms one pair instead of two, because the second 3 has nowhere to be stored separately.
Counting each pair twice
for num in nums:
if k - num in counts:
operations += 1
# without consuming either elementwaiting[partner] -= 1 operations += 1
Without decrementing, the same waiting number pairs with every later match, inflating the count. Each element may take part in exactly one operation, so the partner must be consumed.
Sorting then scanning linearly for partners
nums.sort()
for i in range(len(nums)):
# inner scan for k - nums[i]# hash map in one pass, or true two pointers after sorting
Sorting alone does not help unless you actually converge two pointers; a nested scan is O(n²) and the sort adds O(n log n) on top for nothing.
Edge cases
No partner is ever found, every value simply waits, and the answer is 0.
The first 3 waits, the second finds it — the count-based map handles self-pairing without special casing.
Counts track multiplicity, so two disjoint pairs are formed.
It waits forever and the answer is 0.
The answer is n/2, the theoretical maximum.