Max Number of K-Sum Pairs: Hash Map Complement Counting

You are given an integer array nums and an integer k. In one operation, you can pick two numbers from the array whose sum equals k and remove them. Return the maximum number of operations you can perform on the array.

This is LeetCode 1679: Max Number of K-Sum Pairs, and it is a natural extension of the classic Two Sum problem. Instead of finding one pair, you need to find as many non-overlapping pairs as possible.

Why this problem matters

K-Sum Pairs bridges the gap between "find one pair" (Two Sum) and more advanced pairing problems. It teaches you to think about complement counting with consumption: once a number is used in a pair, it cannot be reused. This pattern appears in scheduling, matching, and resource allocation problems where you need to greedily pair elements under constraints.

It also gives you a clean comparison between two fundamental approaches. The hash map solution runs in O(n) time, while the sort-then-two-pointers solution trades time for space. Understanding when each approach is better is a valuable interview skill.

The key insight

For each number num in the array, its partner must be k - num. If you have already seen k - num and it has not been paired yet, you can form a pair immediately and consume both numbers. If not, you store num in a frequency map for future pairing.

This is the same complement lookup idea from Two Sum, but with a twist: each number can only be used once, so you need to track counts rather than just presence. When you find a complement, you decrement its count in the map (consuming it) instead of just returning a result.

The solution

def max_operations(nums: list[int], k: int) -> int:
    counts = {}
    pairs = 0

    for num in nums:
        complement = k - num
        if counts.get(complement, 0) > 0:
            pairs += 1
            counts[complement] -= 1
        else:
            counts[num] = counts.get(num, 0) + 1

    return pairs

For each number, we check if its complement k - num is available in the frequency map. If it is, we have a match: increment the pair count and decrement the complement's frequency. If the complement is not available, we add the current number to the map so it can be matched by a future element.

The key detail is that we only add num to the map when it does not find a complement. This prevents double counting. If num finds its complement, both are consumed. If it does not, num waits in the map for a future partner.

Visual walkthrough

Notice how the map grows when complements are not found and shrinks when they are. Each number either enters the map or consumes an existing entry. By the end, only unpaired numbers remain in the map.

Complexity analysis

Hash map approach: We iterate through the array once. Each lookup and update in the hash map is O(1) on average. Total time is O(n). The map can hold up to n entries in the worst case (no pairs found), so space is O(n).

Sort + two pointers approach: Sorting takes O(n log n). The two-pointer scan takes O(n). Total time is O(n log n). If you sort in place, the extra space is O(1) (ignoring the sort's internal space). This approach is better when memory is constrained, but the hash map approach is faster for large inputs.

The building blocks

1. Complement lookup with frequency tracking

The core pattern is looking up k - num in a frequency map. This extends the Two Sum hash map technique by tracking counts instead of indices. You decrement on match and increment on miss.

counts = {}
for num in nums:
    complement = k - num
    if counts.get(complement, 0) > 0:
        counts[complement] -= 1
    else:
        counts[num] = counts.get(num, 0) + 1

2. Sort and two-pointer pairing

The alternative approach sorts the array and uses two pointers. If the sum is too small, move the left pointer right. If the sum is too large, move the right pointer left. If the sum equals k, count the pair and move both pointers inward.

def max_operations_two_pointers(nums: list[int], k: int) -> int:
    nums.sort()
    left, right = 0, len(nums) - 1
    pairs = 0

    while left < right:
        total = nums[left] + nums[right]
        if total == k:
            pairs += 1
            left += 1
            right -= 1
        elif total < k:
            left += 1
        else:
            right -= 1

    return pairs

Edge cases

• All elements are the same and equal k / 2: for example, nums = [3, 3, 3, 3] with k = 6. Each pair consumes two 3s, so you get n / 2 pairs. The frequency map handles this because each second occurrence finds the first as its complement.
• No pairs exist: when no two numbers sum to k, every number goes into the map and the pair count stays at 0.
• Array has only one element: you cannot form any pair, so the answer is 0.
• Negative numbers: the complement k - num works correctly with negatives. If nums = [-1, 6] and k = 5, the complement of -1 is 6, which forms a valid pair.
• Duplicate complement values: if nums = [1, 1, 1, 4, 4, 4] and k = 5, you get 3 pairs. The frequency map correctly tracks that each 1 can pair with one 4.

From understanding to recall

The complement counting pattern is simple to understand but easy to get wrong under pressure. The most common mistakes: forgetting to decrement the complement's count after pairing, accidentally adding num to the map even when a pair is found, or not handling the case where num equals its own complement.

Spaced repetition drills these details into muscle memory. You write the frequency map loop from scratch, get immediate feedback on whether you handled consumption correctly, and repeat at increasing intervals. After a few sessions, the pattern is automatic. You do not need to think about the edge cases because your hands already know the code.

Related posts

• Two Sum - The foundational complement lookup problem that this pattern extends from single-pair to multi-pair
• Three Sum - Extends pair finding to triplets using sorting and two pointers, building on the same complement idea
• Contains Duplicate - Uses a hash set for O(n) duplicate detection, the same "have I seen this before?" pattern

CodeBricks breaks Max Number of K-Sum Pairs into its complement-lookup and frequency-tracking building blocks, then drills them independently with spaced repetition. You type the hash map loop and the two-pointer alternative from scratch until both patterns are automatic. When a pairing problem shows up in your interview, you do not hesitate. You just write it.