Least number of unique integers after k removals

November 12, 2022


Problem URL: Least number of unique integers after k removals

We can use a heap to keep track of the frequency of each number. Then we can pop the smallest frequency from the heap until we have removed k numbers. The remaining numbers are the unique numbers.

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = list(collections.Counter(arr).values())
        while k > 0:
            k -= heapq.heappop(heap)
        return len(heap)+1 if k<0 else len(heap)

Time Complexity: O(n+klog(n))
Space Complexity: O(n)