596. Fewest Kinds Left
A collector keeps a shelf of stamps, where nums[i] is the series number of stamp i. A dealer will buy exactly k stamps from the shelf, and the collector may choose which ones to hand over.
After the sale the shelf holds nums.length - k stamps. Return the smallest possible number of different series that can still be on the shelf. If k equals the number of stamps, the shelf is empty and the answer is 0. Your solution should run in O(n log n) time with O(n) extra space.
Example 1
- Input:
- nums = [2,2,3,5,5,5], k = 3
- Output:
- 1
- Explanation:
Selling the single 3 and the two 2s removes two series for 3 stamps, leaving only series 5, so the answer is 1.
Example 2
- Input:
- nums = [1,2,3,4], k = 2
- Output:
- 2
- Explanation:
Every series has one stamp, so selling 2 stamps eliminates 2 series and leaves 2.
Example 3
- Input:
- nums = [7,7,7,8,8], k = 1
- Output:
- 2
- Explanation:
Selling one stamp cannot eliminate any whole series, so both series remain and the answer is 2.
Constraints
1 ≤ nums.length ≤ 200000-109 ≤ nums[i] ≤ 1090 ≤ k ≤ nums.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)