Maximize disjoint k-sum pairs

You are given an integer array nums and an integer k. In one operation you may remove two indices i < j if nums[i] + nums[j] == k; each index can be used at most once. Return the maximum number of operations you can perform. Design an O(n) or O(n log n) solution, discuss space–time trade-offs, and provide code in C, C++, Java, or JavaScript.

Maximize disjoint k-sum pairs

You are given an integer array nums and an integer k. In one operation you may remove two indices i < j if nums[i] + nums[j] == k; each index can be used at most once. Return the maximum number of operations you can perform.

The order in which you pick pairs does not change the maximum count, so a single linear pass that greedily matches each value with a previously-seen complement is optimal. Maintain a count of unused values seen so far; for each new value x, if its complement k - x has an unused occurrence, pair them and increment the answer, otherwise record x as available.

Design an O(n) or O(n log n) solution and discuss the space–time trade-offs.

Constraints

• 1 <= nums.length (problem-level); the function must also handle nums.length == 0 by returning 0
• Values and k may be negative or zero
• Each index may participate in at most one operation
• 1 <= nums.length <= 10^5 (typical interview bound)

Examples

Example 1

Input: ([1, 2, 3, 4], 5)
Output: 2

Explanation: Pair (1,4) and (2,3), both summing to 5. Two operations, no index reused.

Example 2

Input: ([3, 1, 3, 4, 3], 6)
Output: 1

Explanation: Only 3+3 = 6 works; there are three 3's, so one pair is formed and the remaining 3, plus 1 and 4, cannot be paired.

Hints

1. The maximum number of disjoint pairs is independent of pairing order, so a greedy single pass suffices — no backtracking is needed.
2. Keep a hash map of unused values seen so far. For each value x, look up k - x; if an unused copy exists, consume it and count one operation, otherwise store x.
3. Self-complement values (where x == k - x, e.g. x = k/2, or x = 0 with k = 0) just pair up among themselves naturally because the map count is decremented as you match.
4. Sorting plus two pointers (one from each end moving toward a target sum) is an O(n log n) alternative with O(1) extra space — useful when memory is tight.