Max Number of K-Sum Pairs

Max Number of K-Sum Pairs

What is this problem about?

The Max Number of K-Sum Pairs problem provides an integer array nums and an integer k. In a single operation, you can pick two numbers from the array that add up to exactly k and remove them from the array. Your goal is to return the maximum number of operations (pairs) you can perform on the array.

Why is this asked in interviews?

This is a popular variation of the classic "Two Sum" problem. Interviewers ask it because it tests a candidate's ability to count and consume paired data. Unlike "Two Sum" which just asks if a pair exists, this problem requires managing the "exhaustion" of elements, evaluating your skills with Hash Maps (frequency tracking) or Sorting with Two Pointers.

Algorithmic pattern used

There are two highly optimal patterns:

1. Hash Map (Frequency Counting): Iterate through the array. For each number, calculate its complement = k - num. Check the map to see if the complement is available ($> 0$). If it is, you've found a pair! Increment your operation count and decrement the complement's count in the map. If it's not, add the current number to the map. (Time: $O(N)$, Space: $O(N)$).
2. Sorting + Two Pointers: Sort the array. Place left pointer at start and right at end. If sum == k, you have a pair (increment count, move both pointers). If sum < k, move left up. If sum > k, move right down. (Time: $O(N \log N)$, Space: $O(1)$).

Example explanation

Let's use the Hash Map approach on nums = [3, 1, 3, 4, 3], k = 6. Initialize Map: {}. Count = 0.

• num = 3: Complement 6 - 3 = 3. Map has no 3. Add to map. Map: {3: 1}.
• num = 1: Complement 5. Not in map. Map: {3: 1, 1: 1}.
• num = 3: Complement 3. It IS in the map (count is 1)! We pair them up.
  • Count becomes 1.
  • Decrement 3 in map. Map: {3: 0, 1: 1}.
• num = 4: Complement 2. Not in map. Map: {..., 4: 1}.
• num = 3: Complement 3. Map has 3, but count is 0. Cannot pair. Add to map. Map {..., 3: 1}. Total operations = 1.

Common mistakes candidates make

A very common mistake when using a Hash Map is adding all elements to the map first, and then looping through again to find pairs. This often leads to double-counting a number pairing with itself (e.g., if $k=6$ and the array has a single 3, the algorithm might pair it with itself if you aren't strictly managing frequencies). The single-pass approach (check first, then add) elegantly prevents self-pairing bugs.

Interview preparation tip

For the Max Number of K-Sum Pairs interview question, ask the interviewer if the array is already sorted or if memory is constrained. If space is $O(1)$, instantly write the Two Pointers solution. If time is paramount and extra space is allowed, write the single-pass Hash Map solution. Being able to effortlessly switch between these two "Two Sum" architectures guarantees a strong technical rating.