Minimum Unique IDs After Removals

Problem You have a bag of ids (with duplicates) and must remove exactly m items. Return the minimum possible number of distinct ids remaining.

Input / Output

• Input: int array ids, integer m (0 <= m <= |ids|).
• Output: minimum count of distinct ids left after removing m items.

Constraints

• |ids| up to 10^5; O(n log n) expected.

Example

• ids = [2,3,1,1,1,3,4], m = 2 → 2 (remove the single 2 and the single 4; ids 1 and 3 remain).

Expected approach

• Greedy: count frequencies, sort the counts ascending, and spend removals eliminating whole smallest groups first; a partially removed group still counts as distinct, so partial spends are wasted. Answer = distinct − (groups fully removed). O(n log n) time, O(n) space. Be ready to justify the exchange argument for why smallest-first is optimal.