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
Max number of k sum pairs counts how many pairs summing to k can be removed from an array, where each element is used at most once. The removal constraint is what separates this from ordinary pair counting.
Two approaches work, and they differ in what they exploit.
The hash map version scans once, keeping counts of values seen so far. For each element, if its complement k − num is available, pair them off and decrement the complement's count; otherwise record the current value for a later match. Decrementing is what enforces single use — without it, one element pairs with many partners and the count is inflated.
The two-pointer version sorts first, then converges from both ends:
- If the two ends sum to k, count a pair and move both inwards; if the sum is too small move left inwards, and if too large move right inwards.
Moving both pointers on a match is the detail that enforces the constraint — advancing only one leaves an already-used element in play.
The sorted order makes the direction decision unambiguous: a sum below k can only be raised by taking a larger left value, and a sum above k only lowered by taking a smaller right value.
The hash map is O(n) time and O(n) space; sorting makes the two-pointer version O(n log n) time and O(1) space. Neither dominates — the choice depends on whether time or space is tighter.
Duplicates are handled naturally by both, since counts and positions are tracked rather than distinct values.
'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).
Note the single-use constraint
Each element can join at most one pair, which is what distinguishes this from plain pair counting. Both approaches must enforce it explicitly.
Count complements in a map
Scanning once, check whether k - num is available. If so, pair them; otherwise record the current value for a later match.
Decrement after pairing
Reduce the complement's count when a pair is formed. Without this, one element pairs with many partners and the total is inflated.
Or sort and converge
Sort, then place pointers at both ends. The sorted order makes the direction unambiguous — a small sum needs a larger left value, a large sum a smaller right one.
Move both pointers on a match
When the ends sum to k, count the pair and advance both pointers. Moving only one leaves an already-used element available.
Cost of each approach
The map is O(n) time, O(n) space; the two-pointer version is O(n log n) time, O(1) space. Neither dominates — pick by whichever resource is tighter.
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.