Remove exactly elements from an array so that the number of distinct integers left is as small as possible.
Problem
You are given an integer array arr and an integer k.
In one move, you may remove any single element from the array. After performing exactly k removals, return the minimum possible number of distinct integers remaining in the array.
The goal is not to minimize the final array length; it is to eliminate as many different values as possible by removing all occurrences of low-frequency values first.
Key idea
A value disappears only when all of its occurrences are removed. Use the removal budget on values with the smallest frequencies first.
Input Format
- An integer array
arr - An integer
k
You may assume the input follows the usual interview-style constraints for this problem.
Output Format
- Return an integer: the minimum number of unique integers remaining after exactly
kremovals.
Constraints
1 <= arr.length0 <= k <= arr.length- Elements of
arrcan be any integers
Exact platform constraints are not provided here; use standard interview assumptions.
Example 1
Input
arr = [5,5,4], k = 1
Output
1
Explanation
Remove one 5 to get [5,4]. The distinct integers are {5,4}, so the answer is 2? Wait, better choice is to remove 4, leaving [5,5] with only 1 distinct integer. Thus the minimum is 1.
Example 2
Input
arr = [4,3,1,1,3,3,2], k = 3
Output
2
Explanation
Frequencies are: 1 -> 2, 2 -> 1, 3 -> 3, 4 -> 1. Remove all of 2 and 4 using 2 deletions, then remove one 1 or one 3 with the last deletion. The minimum number of distinct integers left is 2.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.