BinarySearch 0382 Minimize Number of Unique Integers After Removals

Problem statement

https://binarysearch.com/problems/Minimize-Number-of-Unique-Integers-After-Removals/

Solution

Calculate frequencies, then remove the smallest ones.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, items, n):
        cnt = sorted(list(Counter(items).values())) + [float("inf")]
        i = 0
        while True:
            if cnt[i] <= n:
                n -= cnt[i]
                i += 1
            else:
                return len(cnt) - i - 1