657. The Most Pairs You Can Remove

Repeatedly choose two values that add to k and remove them both. Each value may be used in at most one pair.

Print the largest number of removals possible.

1 2 3 4, k = 5 -> 2 (1,4) and (2,3) 3 1 3 4 3, k = 6 -> 1 only (3,3) 1 1 1 1, k = 2 -> 2

## The sweep

Sort, converge, and take every exact match:

i = 0, j = n-1, c = 0 while i < j: s = a[i] + a[j] s == k -> c += 1; i += 1; j -= 1 s < k -> i += 1 s > k -> j -= 1

## Why taking every match is safe

The non-matching moves are the 605 argument: a sum below k retires a[i], since a[j] is its largest remaining partner; a sum above retires a[j].

The matching move needs its own argument. Suppose an optimal removal does NOT pair a[i] with a[j], even though they sum to k. There are three cases:

· neither is used: pairing them adds a removal, so it was not optimal · one is used, say a[i] with some p: then a[j] is unused, and swapping to pair a[i] with a[j] while leaving p unused keeps the same count · both are used, a[i] with p and a[j] with q: then a[i] + p = k and a[j] + q = k, so p = a[j] and q = a[i] in value. Re-pairing as (a[i], a[j]) and (p, q) keeps both sums at k and the same count

So an optimal solution always exists that takes this pair, and the greedy loses nothing.

## Why it is pairs, not positions

Each value is consumed, so a value present three times can appear in at most one pair with itself plus pairs with others. 3 1 3 4 3 with k = 6 answers 1: two of the three threes pair up and the last has no partner.

That input is the one to trace, because a solution counting matching VALUES rather than consuming them reports more.

## Boundaries

A single value can form no pair. Values that all equal k / 2 pair up in twos, so four of them give 2 and three give 1.

## Cost

Time O(n log n) for the sort. Space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 2 * 10^9` - `1 ≤ each value ≤ 10^9`