Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.


 
Example 1:
Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
 
Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

Difficulty: interview

Starter code:

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:

Solutions:
# O(n) time and space
# Hashmap and array
# Count number then count occurrence:
# Count the occurrences of each number using HashMap;
# Keep a count of different occurences
# From small to big, for each unvisited least frequent element, deduct from k the multiplication with the number of elements of same occurrence, check if reaching 0, then deduct the corresponding unique count remaining.
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = collections.Counter(arr)
        distinct = len(freq)
        freq_count = collections.Counter(list(freq.values()))
        
        idx = 1
        while k>0:
            if k - idx*freq_count[idx] >= 0:
                k -= idx*freq_count[idx]
                distinct -= freq_count[idx]
                idx += 1
            else:
                # can't remove all, but can remove partially
                # [2,4,1,8,3,5,1,3], 3
                return distinct - k // idx
        return distinct
                
        


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = Counter(arr)
        unique = len(count)
        for v in sorted(count.values()):
            if v <= k:
                unique -= 1
                k -= v
            else:
                break
        return unique

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        char_freq_map = {}
        for num in arr:
            if num in char_freq_map:
                char_freq_map[num] += 1
            else:
                char_freq_map[num] = 1
        
        freq_to_char_map = {}
        freqs = []
        for key in char_freq_map:
            if char_freq_map[key] in freq_to_char_map:
                freq_to_char_map[char_freq_map[key]].append(key)
            else:
                freqs.append(char_freq_map[key])
                freq_to_char_map[char_freq_map[key]] = [key]
        
        i = 0
        freqs.sort()
        ans = 0
        while(1):
            if k == 0:
                break
            freq = freqs[i]
            if k >= len(freq_to_char_map[freq])*freq:
                k -= len(freq_to_char_map[freq])*freq
                i += 1
            else:
                ans += len(freq_to_char_map[freq]) - k//freq
                k = 0
                i += 1
        
        print(freq_to_char_map)
        while(i < len(freqs)):
            ans += len(freq_to_char_map[freqs[i]])
            i += 1
        return ans 

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        #heap with key to be count of each number
        d = defaultdict(int)
        for i in arr:
            d[i] += 1
        
        heap = []
        for key, val in d.items():
            heappush(heap, (val, key))
        if k == 0:
            return len(heap)
        while k > 0:
            if not heap:
                return 0
            count = heappop(heap)[0]
            if k < count:
                res = len(heap) + 1
                break
            elif k == count:
                
                res = len(heap)
                break
            else:
                k -= count
        return res

import heapq
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        nums = {}
        
        for i in arr:
            
            if i in nums:
                nums[i] += 1
            else:
                nums[i] = 1
        
        # print(nums)
        
        
        queue = [ (nums[i], i) for i in nums]
        
        # print(queue)
        
        heapq.heapify(queue)
        
        # print(queue)
        
        while len(queue) > 0 and k > 0:
            
            count, n = heapq.heappop(queue)
            
            if k >= count:
                k = k - count
            else:
                # print('yes', queue, count, n, k)
                count = count - k
                k = 0
                heapq.heappush(queue, (count, n))
                # print(queue)
            
        
        # print(queue)
        
        return len(queue)
        


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = Counter(arr)
        items = sorted(list(counter.items()), key=lambda x: -x[1])
        left = k
        while left > 0 and items:
            if items[-1][1] <= left:
                left -= items[-1][1]
                items.pop()
            else:
                break
        return len(items)



class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr,key = lambda x:(c[x],x))
        return len(set(s[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        
        
        count = Counter(arr)
        nums = [(v, k) for k, v in list(count.items())]
        heapq.heapify(nums)
        for _ in range(k):
            v, k = heapq.heappop(nums)
            if v > 1:
                heapq.heappush(nums, (v-1, k))
        return len(nums)


from collections import Counter


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        L = len(arr)
        d = [[] for _ in range(L+1)]
        counter = Counter(arr)

        for key, count in list(counter.items()):
            d[count].append(key)
        
        for count in range(L+1):
            if k == 0:
                break

            while d[count] and k >= count:
                item = d[count].pop()
                del counter[item]
                k -= count

        return len(counter)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counts = collections.Counter(arr)
        arr.sort()
        arr1 = sorted(arr, key=lambda x: counts[x])
        print(arr1)
        if k != 0:
            del arr1[:k]
            
        return len(set(arr1))

from collections import Counter
import heapq
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        arrCount = Counter(arr)
        heap = []
        for num in arr:
            heapq.heappush(heap, (arrCount[num], num))
        
        while k > 0:
            num = heapq.heappop(heap)[1]
            arrCount[num] -= 1
            if arrCount[num] == 0:
                del arrCount[num]
            k-=1
        return len(arrCount)    

from collections import Counter
import heapq

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = Counter(arr)
        count_num = []
        for num, count in freq.items():
            count_num.append((count, num))
        heapq.heapify(count_num)
        print(count_num)
        while k > 0:
            count, num = heapq.heappop(count_num)
            k -= count
        if k == 0:
            return len(count_num)
        elif k < 0:
            return len(count_num) + 1

class Solution:
    def findLeastNumOfUniqueInts(self, arr, k):
        c = Counter(arr)
        s = sorted(arr, key = lambda x: (c[x],x))
        return len(set(s[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        nums = {}
        
        for i in arr:
            
            if i in nums:
                nums[i] += 1
            else:
                nums[i] = 1
        
        # print(nums)
        
        import heapq
        
        queue = [ (nums[i], i) for i in nums]
        
        # print(queue)
        
        heapq.heapify(queue)
        
        # print(queue)
        
        while len(queue) > 0 and k > 0:
            
            count, n = heapq.heappop(queue)
            
            if k >= count:
                k = k - count
            else:
                # print('yes', queue, count, n, k)
                count = count - k
                k = 0
                heapq.heappush(queue, (count, n))
                # print(queue)
            
        
        # print(queue)
        
        return len(queue)
        


import collections
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = collections.Counter(arr)
        
        value_counter = collections.Counter(list(counter.values()))
        remaining = len(counter)
        
        for val_count_key in range(1, len(arr) + 1):
            if k >= val_count_key * value_counter[val_count_key]:
                k -= val_count_key * value_counter[val_count_key]
                remaining -= value_counter[val_count_key]
            else:
                return remaining - k//val_count_key
            
        return remaining
        
        
        


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnts = Counter(arr)
        
        sorted_cnts = sorted(cnts.items(), key=lambda x: x[1])
        for key, val in sorted_cnts:
            if val <= k:
                del cnts[key]
                k -= val
            else:
                break
        return len(cnts)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        A = dict(Counter(arr))
        B = [(item, A[item]) for item in A]
        B.sort(key=lambda x:x[1], reverse = True)
        result = len(B)
        while k > 0:
            if k >= B[-1][1]:
                k -= B[-1][1]
                result -= 1
                B.pop()
            else:
                k = 0
        return result

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = defaultdict(lambda : 0)
        for i in arr:
            freq[i] += 1
        tup = []
        for i in freq:
            tup.append((freq[i], i))
        tup = sorted(tup)
        count = len(freq)
        
        for i in tup:
            k -= i[0]
            if k < 0:
                break
            count -= 1
        return count


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        temp = sorted(c, key= lambda x: (c[x], -x))
        for i in temp:
            if k > 0:
                k -= c[i]
                if k < 0:
                    c[i] = -k
                else:
                    c[i] = 0
        return sum(c[i] > 0 for i in c)
                


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        if k == len(arr):
            return 0
        d = dict()
        for i in arr:
            if i in list(d.keys()):
                d[i] += 1
            else:
                d[i] = 1
        lst = [[v, k] for k, v in list(d.items())]
        lst.sort()
        res = []
        for i in lst:
            for _ in range(i[0]):
                res.append(i[1])
        return len(set(res[k:]))


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        d = {}
        
        for i in arr:
            if i in d:
                d[i]+=1
            else:
                d[i]=1
                
        values  = [[v,k] for k,v in list(d.items())]
        
        values.sort()
        
        for i in values:
            if i[0] <=k:
                k = k - i[0]
                i[0] = 0
        count = 0
        for i in values:
            if i[0]!=0:
                count = count +1
        return count


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        import collections
        d = collections.Counter(arr).most_common()[::-1]
        for i in range(len(d)):
            k -= d[i][1]
            if k < 0:
                return len(d) - i
        return 0


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        if k >= len(arr) - 1:
            return len(arr) - k

        counter = sorted(Counter(arr).values())
        print(counter)
        ptr = 0
        while k >= 0:
            k -= counter[ptr]
            ptr += 1
        
        return len(counter) - ptr + 1


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:

        # create a dictionary of {number: count}
        num_count_dict = {}
        for num in arr:
            if num in num_count_dict:
                num_count_dict[num] += 1
            else:
                num_count_dict[num] = 1
                
        # create a dictionary of {count: a_list_of_number}
        num_dict = {}
        for num in num_count_dict.keys():
            count = num_count_dict[num] 
            if count in num_dict:
                num_dict[count].append(num)
            else:
                num_dict[count] = [num]
        
        # sorted num_dict by each number's count
        sorted_num_by_count = sorted(num_count_dict.items(), key=lambda x: x[1])
        print(sorted_num_by_count)
        for i in range (0, len(sorted_num_by_count)):
            num = sorted_num_by_count[i][0] # get dict key
            #print('num={}, k={}, num_count_dict={}'.format(num, k, num_count_dict[num]))
            num_count = num_count_dict[num]
            if num_count <= k:
                del num_count_dict[num]
            else:
                num_count_dict[num] = num_count_dict[num]-k
            k = k-num_count
            if k == 0:
                break
        return len(num_count_dict)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr,key = lambda x:(c[x],x))
        print(s)
        return len(set(s[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = {}
        for id in arr:
            counter[id] = counter.get(id, 0) + 1
        id2count = sorted([[count, id] for id, count in counter.items()], key=lambda x: (-x[0], x[1]))
        for i in range(len(id2count) - 1, -1, -1):
            count = id2count[i][0]
            if k - count < 0:
                break
            id2count.pop()
            k -= count
        return len(id2count)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = defaultdict(int)
        for num in arr: freq[num] += 1
        freq_arr = []
        for t, v in freq.items():
            freq_arr.append([v,t])
        freq_arr.sort(reverse= True)
        while k > 0:
            amount, rem = freq_arr.pop()
            if amount <= k:
                del freq[rem]
                k -= amount
            else:
                freq[rem] = amount - k
                k = 0
        return len(freq)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freqm = collections.defaultdict(int)
        
        for a in arr:
            freqm[a] += 1
            
        heap = []
        
        for key, val in freqm.items():
            heapq.heappush(heap, (val, key))
            
        totalKeys = len(heap)
        count = 0
        
        while k > 0 and heap:
            val, key = heapq.heappop(heap)
            if k >= val:
                k -= val
                count += 1
            else:
                break
        
        return totalKeys - count

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        if not arr:
            return 0
        
        dic = collections.defaultdict(int)
        for n in arr:
            dic[n] += 1
        
        l = []
        
        for key, val in dic.items():
            l.append([key,val])
            
        l.sort(key = lambda x: x[1])
        # print(l)
        count = len(l)
        
        for i in range(len(l)):
            if k == 0:
                break
            n = min(k, l[i][1])
            l[i][1] -= n
            k -= n
            if l[i][1] == 0:
                count -= 1
                i -= 1
            
        # print(l)
        return count

from collections import Counter

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        # im going to use a map, and we need to sort the map based on 
        m = Counter(arr)
        
        for x,y in sorted(list(m.items()), key=lambda x: x[1]):
            if k < 1:
                break
            
            a = max(y-k, 0)
            if a == 0:
                m.pop(x)
            k = max(k-y, 0)
        
        return len(m)
            



class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = collections.Counter(arr)
        for i,value in sorted(counter.items(), key = lambda x: x[1]):
            val = k
            k -= value
            counter[i] -= val
            if counter[i] <= 0:
                del counter[i]
        return len(counter)

from collections import OrderedDict

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        # im going to use a map, and we need to sort the map based on 
        m = {}
        for i in arr:
            m[i] = m.get(i, 0) +1
        
        for x,y in sorted(list(m.items()), key=lambda x: x[1]):
            if k < 1:
                break
            
            a = max(y-k, 0)
            if a == 0:
                m.pop(x)
            k = max(k-y, 0)
        
        return len(m)
            



class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        dic, a = {}, []
        for x in arr:
            dic[x] = dic.get(x, 0) + 1
        for x in dic:
            a.append(dic[x])
        a.sort(reverse = True)
        while a:
            x = a.pop()
            if x > k:
                return len(a) + 1
            k -= x
        return 0
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
#         dic, count = {}, []
#         for x in arr:
#             dic[x] = dic.get(x,0)+1
        
#         for x in dic:
#             count.append(dic[x])
#         count.sort(reverse = True)
#         while k > 0 and count:
#             if k - count[-1] >= 0:
#                 k -= count[-1]
#                 count.pop()
#             else:
#                 k -= count[-1]

#         return(len(count))
                
                


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr,key = lambda x:(c[x],x))
        return len(set(s[k:]))


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnts = collections.Counter(arr)
        heap = [(v, k) for k, v in cnts.items()]
        heapq.heapify(heap)
        for _ in range(k):
            cnt, val = heapq.heappop(heap)
            cnt -= 1
            if cnt != 0:
                heapq.heappush(heap, (cnt, val))

        return len(heap)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        c = collections.Counter(arr)
        for n in sorted(c, key = lambda num: c[num]):
            if c[n] <= k:
                k -= c[n]
                del c[n]
            else:
                break
        
        return len(c)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        if k==len(arr):
            return(0)
        
        countDict = dict()
        
        for x in arr:
            if x not in countDict:
                countDict[x] = 0
            countDict[x] += 1
            
        from heapq import heappush, heappop, heapify
        
        minHeap = []
        
        for x in list(countDict.keys()):
            heappush(minHeap, [countDict[x], x])
        
        while(k>0):
            if k>=minHeap[0][0]:
                k -= minHeap[0][0]
                heappop(minHeap)
            else:
                if len(minHeap)==1:
                    minHeap[0][0] -= k
                    k = 0
                else:
                    k = 0
                    
        return(len(minHeap))
                    


from collections import Counter


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr, key = lambda x:(c[x],x))
        return len(set(s[k:]))


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = collections.Counter(arr)
        
        arr = list(reversed([item for items, c in count.most_common() for item in [items] * c]))
        
        #print(arr, arr[k:])
        return len(collections.Counter(arr[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        import heapq
        
        vals = {}
        
        for val in arr:
            if val in vals:
                vals[val] += 1
            else:
                vals[val] = 1
        
        hp = []
        for val in vals:
            hp.append(vals[val])
        
        heapq.heapify(hp)
    
        #count represents the number of elements popped
        while(k > 0 and len(hp)):
            curr = heapq.heappop(hp)
            if curr <= k:
                k = k - curr
            else:
                k = curr - k
                heapq.heappush(hp, k)
                break
        return len(hp)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        mapp = {}
        for item in arr:
            if item in list(mapp.keys()):
                mapp[item] += 1
            else:
                mapp[item] = 1
                
        sort_mapp = {c: v for c, v in sorted(list(mapp.items()), key=lambda x: x[1])}
        
        for c, v in list(sort_mapp.items()):
            if v - k > 0:
                sort_mapp[c] -= k
                break
            else:
                k = (v - k) * -1
                sort_mapp[c] = 0
                if k <= 0:
                    break
                
        count = 0
        for c, v in list(sort_mapp.items()):
            if v > 0:
                count += 1
                
        return count


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = collections.Counter(arr)
        key = sorted(cnt, key = lambda x: cnt[x])
        n_unique = len(key)
        # print(key)
        for i in range(n_unique):
            # print(key[i])
            k = k-cnt[ key[i] ]
            if k<0:
                return n_unique-i
            elif k == 0:
                return n_unique-i-1
        
        return 0

from collections import Counter
from collections import deque
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = Counter(arr)
        count = deque(sorted([(count[k], k) for k in count]))
        # print(count)
        while count and k >= count[0][0]:
            k-=count.popleft()[0]
        return len(count)
                


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = collections.Counter(arr)
        
        for cnt, num in sorted((v,k) for k, v in c.items()):
            if cnt <= k:
                del c[num]
                k -= cnt
        
        return len(c)

class CountClass:
    def __init__(self, value, frequency):
        self.value = value
        self.frequency = frequency
    def __lt__(self, other):
        return self.frequency < other.frequency
    def getValue(self):
        return self.value
    def getFrequency(self):
        return self.frequency
    
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        if not arr:
            return 0
        
        import heapq
        
        # This map will keep track of the counts
        records = {}
        # Initiate the min-heap
        q = []
        
        # Saving the counts
        for i in arr:
            if i not in list(records.keys()):
                records[i] = 0
            records[i] += 1
          
        for key, value in list(records.items()):
            heapq.heappush(q, CountClass(key, value))
        
        while k != 0 and q:
            node = heapq.heappop(q)
            key = node.getValue()
            val = node.getFrequency()
            if val == 1:
                del records[key]
            else:
                val -= 1
                heapq.heappush(q, CountClass(key, val))
            k -= 1
        
        return len(records)
        
        
        
        
        
        


from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = Counter(arr)
        arr = sorted(arr, key = lambda x: (count[x], x))
        return len(set(arr[k:]))

import heapq
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        counter = collections.Counter(arr)
        heap = [(value, key) for key, value in list(counter.items())]
        
        heapq.heapify(heap)
        
        while k > 0:
            k -= heapq.heappop(heap)[0]
        
        return len(heap) + (k < 0)
        


import queue

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        temp = {}
        for n in arr:
            if n not in temp:
                temp[n] = 0
            temp[n] += 1
        
        q = queue.PriorityQueue()
        for n, c in temp.items():
            q.put((c, n))
        
        while k > 0:
            c, n = q.get()
            if k < c:
                q.put((c, c - k))
                break
            k -= c
        
        return len(q.queue)

from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr, key=lambda x: (c[x], x))
        return len(set(s[k:]))

import queue


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:

        counter = {}
        for i in arr:
            if counter.__contains__(i):
                counter[i] += 1
            else:
                counter[i] = 1
        q = queue.PriorityQueue()
        for i in counter:
            q.put((counter[i], i))

        lastCutted = True
        while k > 0:
            element = q.get()
            count = element[0]
            if k >= count:
                lastCutted = True
            else:
                lastCutted = False
            k -= count

        if lastCutted:
            return q.qsize()
        else:
            return q.qsize() + 1

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        if k==len(arr):
            return(0)
        
        countDict = dict()
        
        for x in arr:
            if x not in countDict:
                countDict[x] = 0
            countDict[x] += 1
            
        from heapq import heappush, heappop, heapify
        
        minHeap = []
        
        for x in list(countDict.keys()):
            heappush(minHeap, [countDict[x], x])
        
        while(k>0):
            if k>=minHeap[0][0]:
                k -= minHeap[0][0]
                heappop(minHeap)
            else:
                k -= minHeap[0][0]
                
        return(len(minHeap))
                    


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        d = {}
        for num in arr:
            try:
                d[num] += 1
            except:
                d[num] = 1
        heap = []
        
        for key in list(d.keys()):
            heapq.heappush(heap, (d[key], key))
        
        while k:
            popped = heapq.heappop(heap)
            key = popped[1]
            d[key] -= 1
            if not d[key]:
                del d[key]
            else:
                heapq.heappush(heap, (d[key], key))
            k -= 1
        
        return len(list(d.keys()))


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        a=collections.Counter(arr)
        b=sorted(a,key=lambda x:a[x])
        i=0
        while k:
            if a[b[i]]<=k:
                k-=a[b[i]]
                del b[i]
            else:
                k=0
        return len(b)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        if len(arr) == 0:
            return 0
        #sa = list(set(arr))
        arrcounts = collections.Counter(arr)#[(x, arr.count(x)) for x in sa]
        #print(arrcounts)
        #arrcounts.sort(key = lambda x:x[1])
        arrcounts = sorted(arrcounts.items(), key = lambda x: x[1])
        i = k
        j = 0
        #print(arrcounts)
        while i > 0 and j < len(arrcounts):
            i -= arrcounts[j][1]
            if i >= 0:
                arrcounts.pop(j)
            else:
                j += 1
        #print(arrcounts)
        return len(arrcounts)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count=Counter(arr)
        temp=sorted(arr,key=lambda x:(count[x],x))
        return len(set(temp[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        dic = {}
        for i in arr:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        keys = dic.keys()
        keys = sorted(keys, key=lambda a: dic[a])
        for index in range(len(keys)):
            if k == 0:
                return len(keys)-index
            elif k-dic[keys[index]] < 0:
                return len(keys)-index
            else:
                k -= dic[keys[index]]
        return 0

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        h={}
        for e in arr:
            if e in h:
                h[e] +=1
            else:
                h[e] =1
        l=list(h.values())
        l.sort()
        while k>0:
            k= k-l[0]
            if k>=0:
                l.pop(0)
        return len(l)                


from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)
        cnt = sorted(cnt.values())
        while k > 0:
            num = cnt.pop(0)
            k -= num
        if k < 0:
            return len(cnt)+1
        elif k == 0:
            return len(cnt)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = collections.Counter(arr)
        cnt = sorted(cnt.values())
        while cnt:
            num = cnt.pop(0)
            k -= num
            if k < 0:
                return len(cnt)+1
            elif k == 0:
                return len(cnt)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = collections.Counter(arr)
        cnt = sorted(cnt.values())
        while k > 0:
            num = cnt.pop(0)
            k -= num
        if k < 0:
            return len(cnt)+1
        elif k == 0:
            return len(cnt)


from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)
        cnt = sorted(cnt.values())
        while k>0:
            num = cnt.pop(0)
            k -= num
        if k < 0:
            return len(cnt)+1
        elif k == 0:
            return len(cnt)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        dic={}
        for i in arr:
            if i not in dic:
                dic[i]=1
            else:
                dic[i]+=1
        stack=[u for u in dic.values()]
        stack.sort()
        L=len(stack)
        ans=0
        while k>0:
            test=stack.pop(0)
            if test<=k:
                ans+=1
            k-=test         
        return L-ans

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = {}
        for num in arr:
            if num not in count:
                count[num] = 0
            count[num] += 1
        
        values = sorted([v for v in count.values()])
        for _ in range(k):
            values[0] -= 1
            if values[0] == 0:
                del values[0]
        return len(values)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        dic=collections.defaultdict(int)
        for i in range(len(arr)):
            dic[arr[i]]+=1
        num=[]
        total=0
        for key in list(dic.keys()):
            num.append(dic[key])
            total+=1
        num.sort()
        count=0
        while(k>0 and num):
            k-=num[0]
            num.pop(0)
            if k<0:
                break
            count+=1
        return total-count
        


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        arr.sort()
        occ = []
        count = 1
        for i in range(1,len(arr)):
            if arr[i]==arr[i-1]:
                count += 1
            else:
                occ.append(count)
                count = 1
        occ.append(count)
        occ.sort()
        res = len(occ)
        for i in occ:
            if i<=k:
                res -= 1
                k -= i
            else:
                break
        return res


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr) 
        return len(set(sorted(arr, key= lambda x: (c[x], x))[k:]))
                


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        dic = {}
        for num in arr:
            if num not in dic:
                dic[num] = 0
            dic[num] += 1
            
        l = [v for k, v in sorted(dic.items(), key = lambda item: item[1])]
        
        while len(l) > 0 and l[0] <= k:
            k -= l.pop(0)
            
        return len(l)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counted_arr = dict(Counter(arr))
        counted_arr = sorted(list(counted_arr.items()), key=lambda kv: kv[1], reverse=False)
        print(counted_arr)
        
        while k > 0 and len(counted_arr) > 0:
            val = counted_arr[0]
            # print(val)
            freq = val[1]
            k -= freq
            
            if k >= 0:
                counted_arr.pop(0)
            
        return len(counted_arr)


#from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        if not arr:
            return 0
        dic = collections.Counter(arr)
        L = sorted(list(dic.values()))
        
        while k>=L[0]:
            k -= L.pop(0)
            if len(L)==0:
                return 0
        return len(L)


from collections import defaultdict

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        nums = defaultdict(int)
        for num in arr:
            nums[num] += 1
        sorted_nums = sorted(nums.items(), key=lambda x: x[1])
        tmp = k
        while tmp > 0:
            n = sorted_nums[0][1]
            if tmp < n:
                break
            tmp -= n
            sorted_nums.pop(0)
        return len(sorted_nums)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counts = {}
        for element in arr:
            if element in counts:
                counts[element] += 1
            else:
                counts[element] = 1
        counts_sorted = sorted(counts.items(), key=lambda x: x[1], reverse=False)
        while len(counts_sorted) > 0 and k >= counts_sorted[0][1]:
            removed = counts_sorted.pop(0)
            k -= removed[1]
        return len(counts_sorted)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        d = dict()
        for num in arr:
            if num in d:
                d[num] += 1
            else:
                d[num] = 1
        
        for key, value in sorted(d.items(), key=lambda item: item[1]):
            if k >= value:
                k -= value
                del d[key]
            else:
                break
        return len(d)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = Counter(arr)
        res = len(counter)
        
        for key in list(sorted(counter.keys(),key=lambda x: counter[x])):
            freq = counter[key]
            if k>=freq:
                res -= 1
                k -= freq
        
        return res

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count=collections.Counter(arr)
        count=sorted(count.values())
        a=len(count)
        for i in count:
            if k>=i:
                k-=i
                a-=1
        return a


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        m = {}
        for a in arr:
            if not a in m:
                m[a] = 1
            else:
                m[a] += 1
        m = dict(sorted(m.items(), key=lambda x: x[1]))
        count = 0
        for key, value in m.items():
            if value <= k:
                m[key] = 0
                k -= value
                count += 1
            else:
                break
        return len(m) - count

from heapq import heappush, heappop
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        d = {}
        for i in arr:
            d[i] = d.get(i,0)+1
          
        heap = []
        for i in d.keys():
            heappush(heap, (d[i]))
            
        while k >0:
            count = heappop(heap)
            k-= count
            if k < 0:
                return len(heap) + 1
            
        return len(heap)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq = {}
        for i in arr:
            if i in freq.keys():
                freq[i] += 1
            else:
                freq[i] = 1
        
        values = []
        frequencies = []
        for key in freq.keys():
            values.append(key)
            frequencies.append(freq[key])
        
        frequencies = sorted(frequencies)
        distinct = len(frequencies)
        ind = 0
        for i in range(distinct):
            k -= frequencies[i]
            if (k < 0):
                return distinct-i
            elif (k == 0):
                return distinct-i-1
            i += 1
            
        return 0

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = collections.Counter(arr)
        
        for elem, cnt in sorted(counter.items(), key = lambda x: x[1]):
            k -= cnt
            if k >= 0:
                del counter[elem]
        return len(counter)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        print(c)
        cnt, remaining = Counter(c.values()), len(c)
        print(cnt)
        
        for key in range(1, len(arr) + 1): 
            print(cnt[key],key)
            if k >= key * cnt[key]:
                k -= key * cnt[key]
                remaining -= cnt[key]
            else:
                #print('In Else during key',key)
                return remaining - k // key
                #print('After Return',key)
        return remaining

class Solution(object):
    def findLeastNumOfUniqueInts(self, arr, numLettersToRemove):
        dictionary = {}

        for num in arr:
            if num in dictionary:
                dictionary[num] = dictionary[num] + 1
            else:
                dictionary[num] = 1

        # Sort Dictionary by Value
        dictionary = {key:value for key,value in sorted(dictionary.items(), key=lambda item: item[1])}
        #print(\"Sorted: \", dictionary)


        keyList = list(dictionary.keys())
        valueList = list(dictionary.values())
        keyPointer = 0
        valuePointer = 0
        while numLettersToRemove > 0:

            if (valueList[valuePointer] > 0):
                valueList[valuePointer] = valueList[valuePointer] - 1

            if valueList[valuePointer] == 0:
                keyPointer += 1
                valuePointer += 1

            #print(\"Key Pointer: \", keyPointer)
            numLettersToRemove -= 1

        outputList = keyList[keyPointer:]


        output = outputList.__len__()

        return output

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        #first creating a dictionary of element counts
        H = dict()
        for element in arr:
            if element in H:
                H[element] += 1 
            else:
                H[element] = 1
        
        #sort the dictionary
        H  = {k: v for k, v in sorted(list(H.items()), key=lambda item: item[1])}
        
        #initialize some useful variables
        S = 0
        M  = len(H)
        c = 0
        for val in list(H.values()):
            S += val
            c += 1
            if S == k:
                return M - c
            elif S > k:
                return M - c + 1
            else:
                continue


from collections import defaultdict
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        di=defaultdict(int)
        for i in arr:di[i]+=1
        p=sorted(list(di.items()),key=lambda x:x[1])
        n=len(p)
        i=0
        while(k>0):
            if k-p[i][1]>=0:
                n-=1
            k-=p[i][1]
            i+=1
        return n
            
            


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        size = 0
        adict = {}
        for item in arr:
            if item not in adict:
                adict[item] = 1
                size += 1
            else: 
                adict[item] += 1
        
        sort = sorted(adict.items(), key=lambda x: x[1])
        
        for i in sort:
            #print(i[1])
            if k >= i[1]:
                #print(i[1])
                k -= i[1]
                size -= 1
                #print(k)
                #print(size)
        
        return size

from collections import Counter

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        mapper = Counter(arr)
        count = 0
        size = len(mapper)
        values = sorted(mapper.values())
        for val in values:
            if val <= k:
                k -= val
                count += 1
            else:
                return size - count
        return size - count

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        # 9:21
        c=collections.Counter(arr)
        items=[(k,v) for k,v in list(c.items())]
        items.sort(key=lambda x:x[1])
        removals=0
        i=0
        while removals<k and i<len(items):
            ky=items[i][0]
            if c[ky]==1:
                del c[ky]
                i+=1
            else:
                c[ky]-=1
            removals+=1
        return len(c)
            
            
            


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        dic = {}
        
        for i in range(len(arr)):
            if(arr[i] in dic):
                dic[arr[i]] += 1
            else:
                dic[arr[i]] = 1
                
        dic = {k: v for k, v in sorted(list(dic.items()), key=lambda item: item[1])}
        
        for i in dic:
            if(k > 0):
                if(k > dic[i]):
                    k -= dic[i]
                    dic[i] = 0
                else:
                    dic[i] -= k
                    k = 0
            else:
                break
         
        ans = 0
        
        for i in dic:
            if(dic[i]>0):
                ans += 1
                
        return ans


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        d={}
        for i in arr:
            if i not in d:
                d[i]=1
            else:
                d[i]+=1
        d=sorted(list(d.items()),key=lambda x:-x[1])
        d=[list(i) for i in d]
        for k0 in range(k):
            d[-1][1]-=1
            if d[-1][1]==0:
                d.pop()
        return len(d)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        bucket = [[] for _ in range(len(arr)+1)]
        counter = collections.Counter(arr)
        for key, value in counter.items():
            bucket[value].append(key)
        for c in range(len(bucket)):
            if k==0:
                break
            while bucket[c] and k>=c:
                del counter[bucket[c].pop()]
                k -= c
        return len(counter)

import collections
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        buckets = [[] for _ in range(len(arr) + 1)]
        counter = collections.Counter(arr)
        for key, count in counter.items():
            buckets[count].append(key)
        for count in range(len(arr) + 1):
            if k == 0: break
            while buckets[count] and k >= count:
                del counter[buckets[count].pop()]
                k -= count
        return len(counter)

from collections import Counter 
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = collections.Counter(arr)
        for i, j in reversed(counter.most_common()):
            if k:
                if k - j >= 0:
                    del counter[i]
                    k -= j
                else:
                    break    
        return len(counter)
            


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = collections.Counter(arr)
        for i,value in sorted(list(counter.items()), key = lambda x: x[1]):
            val = k
            k -= value
            counter[i] -= val
            if counter[i] <= 0:
                del counter[i]
        return len(counter)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = collections.Counter(arr)
        for i,value in sorted(list(counter.items()), key = lambda x: x[1]):
            val = k
            k -= value
            counter[i] -= val
            if counter[i] <= 0:
                del counter[i]
        return len(counter)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        

        dict = {}
        for num in arr:
            dict[num] = dict.get(num,0) + 1
            
            
            
        size = len(arr) + 1
        buckets = [[] for _ in range(size)]
        
                
        for num, freqency in list(dict.items()):
            buckets[freqency].append(num)
            
            
        for i in range(size):
            if k == 0: 
                break
                
            while buckets[i] and k >= i:
                num = buckets[i].pop()
                del dict[num]
                k -= i
        return len(dict)
    
    
#         buckets = [[] for _ in range(len(arr) + 1)]
#         counter = collections.Counter(arr)
#         for key, count in counter.items():
#             buckets[count].append(key)
#         for count in range(len(arr) + 1):
#             if k == 0: break
#             while buckets[count] and k >= count:
#                 del counter[buckets[count].pop()]
#                 k -= count
#         return len(counter)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        counts = defaultdict(list)
        for num, freq in list(c.items()):
            counts[freq].append(num)
        for freq in range(1, len(arr) + 1):
            while counts[freq] and k >= freq:
                del c[counts[freq].pop()]
                k -= freq
        return len(c)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = collections.Counter(arr)
        freq = sorted(counter.values())
        
        ans = len(freq)
        
        for f in freq:
            if k>=f:
                k-=f
                ans-=1
        return ans

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        from collections import Counter
        from heapq import heapify, heappop
        heap = [(val, key) for key, val in list(Counter(arr).items())]
        heapify(heap)
        while k > 0:
            k -= heappop(heap)[0]
        return len(heap) + (k < 0)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        

        dict = {}
        for num in arr:
            dict[num] = dict.get(num,0) + 1
            
    
        size = len(arr) + 1
        counters = [[] for _ in range(size)]
        
                
        for num in dict:
            counters[dict[num]].append(num)
            
        result = len(dict)    
        for i in range(size):
            if k == 0: 
                break
                
            while counters[i] and k >= i:
                num = counters[i].pop()
                #del dict[num]
                result -=1
                k -= i
        return result
    


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        buckets = [[] for _ in range(len(arr) + 1)]
        counter = collections.Counter(arr)
        for key, count in counter.items():
            buckets[count].append(key)
        for count in range(len(arr) + 1):
            if k == 0: break
            while buckets[count] and k >= count:
                del counter[buckets[count].pop()]
                k -= count
        return len(counter)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        

        dict = {}
        for num in arr:
            dict[num] = dict.get(num,0) + 1
            
            
            
        size = len(arr) + 1
        buckets = [[] for _ in range(size)]
        
                
        for num, freqency in list(dict.items()):
            buckets[freqency].append(num)
            
        result = len(dict)    
        for i in range(size):
            if k == 0: 
                break
                
            while buckets[i] and k >= i:
                num = buckets[i].pop()
                result -=1
                k -= i
                
        return result
    


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        buckets = [[] for _ in range(len(arr) + 1)]
        counter = collections.Counter(arr)
        for key, count in list(counter.items()):
            buckets[count].append(key)
        for count in range(len(arr) + 1):
            if k == 0: break
            while buckets[count] and k >= count:
                del counter[buckets[count].pop()]
                k -= count
        return len(counter)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        

        dict = {}
        for num in arr:
            dict[num] = dict.get(num,0) + 1
            
    
        size = len(arr) + 1
        counters = [[] for _ in range(size)]
        
                
        for num in dict:
            counters[dict[num]].append(num)
            
        result = len(dict)    
        for i in range(size):
            if k == 0: 
                break
                
            while counters[i] and k >= i:
                num = counters[i].pop()
                del dict[num]
                result -=1
                k -= i
        return result
    


from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        # trivous solution
        
        # sort numbers by count
        
        num_count = Counter(arr)
        
        sort_nums = list(num_count.most_common())
        
        while sort_nums and sort_nums[-1][1] <= k:
            k -= sort_nums[-1][1]
            sort_nums.pop()
        
        return len(sort_nums)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = collections.Counter(arr)
        
        arr = list(reversed([item for items, c in count.most_common() for item in [items] * c]))
        
        print(arr, arr[k:])
        return len(collections.Counter(arr[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        for key, val in list(collections.Counter(arr).items()):
            heapq.heappush(heap, (val, key))
            
        for _ in range(k):
            val, key = heapq.heappop(heap)
            if val > 1:
                heapq.heappush(heap, (val - 1, key))
        return len(heap)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = [(v, k) for k, v in collections.Counter(arr).items()]
        heapq.heapify(count)
        while k > 0:
            k -= heapq.heappop(count)[0]
        return len(count) if k >= 0 else len(count) + 1

from collections import Counter

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freqDict = Counter(arr)
        values = sorted(list(freqDict.values()))
        sumForK = 0
        for idx, value in enumerate(values):
            if sumForK + value == k:
                return len(values)-idx-1
            elif sumForK + value > k:
                return len(values)-idx
            sumForK += value
        return 0
            


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter= collections.Counter(arr)
        import heapq
        heap= []
        for key in counter:
            heapq.heappush(heap,(counter[key], key))
        
        while (heap and k):
            count, key = heapq.heappop(heap)
            
            if k >= count:
                k -= count
            else:
                return len(heap) +1
        return len(heap)
    
# class Solution(object):
#     def findLeastNumOfUniqueInts(self, arr, k):
#         heap = []
#         count = collections.Counter(arr)
#         for key in count:
#             heapq.heappush(heap, (count[key], key))
        
#         while(heap and k):
#             count, key = heapq.heappop(heap)
#             if k >= count:
#                 k -= count
#             else:
#                 return len(heap) + 1
#         return len(heap)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        for key, val in list(collections.Counter(arr).items()):
            heapq.heappush(heap, (val, key))
            
        while k > 0:
            val, key = heapq.heappop(heap)
            if val > k:
                heapq.heappush(heap, (val - k, key))
                break
            else:
                k -= val
        return len(heap)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        for key, val in list(collections.Counter(arr).items()):
            heapq.heappush(heap, (val, key))
            
        for _ in range(k):
            val, key = heapq.heappop(heap)
            if val > 1:
                heapq.heappush(heap, (val - 1, key))
        return len(heap)



class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        hp = [[val, key] for key, val in collections.Counter(arr).items()]
        heapq.heapify(hp)
        
        while k > 0:
            k -= 1
            hp[0][0] -= 1
            if hp[0][0] == 0:
                heapq.heappop(hp)
            #k -= heapq.heappop(hp)[0]
            
        return len(hp) + (k < 0)   

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        for key, val in list(collections.Counter(arr).items()):
            heapq.heappush(heap, (val, key))
            
        for _ in range(k):
            val, key = heapq.heappop(heap)
            if val > 1:
                heapq.heappush(heap, (val - 1, key))
        return len(heap)

 


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        acnt=collections.Counter(arr)
        nt=[[val,key] for key,val in acnt.items()]
        heapq.heapify(nt)
        while k>0:
            fre,val=heapq.heappop(nt)
            k-=fre
        if k==0: return len(nt)
        return len(nt)+1

class Solution:
    # Time: O(n*log(n))
    # Space: O(n)
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        for key, val in collections.Counter(arr).items():
            heapq.heappush(heap, (val, key))
            
        for _ in range(k):
            val, key = heapq.heappop(heap)
            if val > 1:
                heapq.heappush(heap, (val - 1, key))
        return len(heap)

class Solution:
  def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
    counter = {}

    for item in arr:
      counter[item] = 1 + counter.get(item, 0)

    values = sorted(counter.values())
    
    removed = 0

    for v in values:
      if v > k:
        break
      else:
        k -= v
        removed += 1

    return len(values) - removed

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        from collections import Counter
        from heapq import heappush,heappop
        d=Counter(arr)
        q=sorted(arr,key=lambda x:(d[x],x))
        
        return (len(set(q[k:])))
        
    


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        for key, val in collections.Counter(arr).items():
            heapq.heappush(heap, (val, key))
            
        for _ in range(k):
            val, key = heapq.heappop(heap)
            if val > 1:
                heapq.heappush(heap, (val - 1, key))
        return len(heap)

import heapq

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        counter = collections.Counter()
        for num in arr:
            counter[num] = counter[num] + 1
            
        for num,cnt in counter.items():
            heapq.heappush(heap, (cnt, num))
            
        while k > 0:
            top = heapq.heappop(heap)
            if k >= top[0]:
                k -= top[0]
            else:
                heapq.heappush(heap, top)
                k = 0
        return len(heap)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        from collections import Counter
        
        d=Counter(arr)
        q=sorted(arr,key=lambda x:(d[x],x))
        
        return (len(set(q[k:])))
        
    


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        counts = collections.Counter()
        for num in arr:
            counts[num] += 1
        
        for num,cnt in counts.items():
            heapq.heappush(heap, (cnt, num))
            
        while k > 0:
            top = heapq.heappop(heap)
            if k >= top[0]:
                k -= top[0]
            else:
                heapq.heappush(heap, top)
                k = 0
        return len(heap)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        from collections import Counter
        
        counter = Counter(arr)
        
        counter = sorted(counter.most_common(),key=lambda x: (x[1],x[0]),reverse=True)
        
        #print(counter)
        
        while k > 0 and counter:
            
            #counter[-1][1] -= 1
            
            edge = list(counter[-1])
            
            edge[1] -= 1
            
            counter[-1] = tuple(edge)
            
            if counter[-1][1] == 0:
                counter.pop()
             
            k -= 1
        
        return len(counter)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        dic = collections.Counter(arr)
        arrs = sorted(arr, key=lambda x: (-dic[x], x))
    
        for i in range(k):
            arrs.pop()
        return len(set(arrs))

from collections import Counter

class Solution:

    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        counter = Counter(arr)
        freq_sorted = sorted(arr, key=lambda x: (counter[x],x))
        return len(set(freq_sorted[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        d = {}
        for i in range(len(arr)):
            if arr[i] in d:
                d[arr[i]] += 1
            else:
                d[arr[i]] = 1
                
        m = sorted(d.values())
        ans = len(m)
        for c in m:
            if k >= c:
                k -= c
                ans -= 1
        return ans


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        freqs = collections.Counter(arr)
        #{1: 2 , 2:1 , 3:3, 4:1}
        
        heap = []
        
        for key, val in list(freqs.items()):
            heapq.heappush(heap, [val, key])
            
        while k > 0:
            heap[0][0] -= 1
            if heap[0][0] == 0:
                heapq.heappop(heap)
            k -= 1
        
        return len(heap)
            


from collections import Counter
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr,key = lambda x:(c[x],x))
        return (len(set(s[k:])))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        dic = collections.Counter(arr)
        for element, count in list(dic.items()):
            heapq.heappush(heap, [count, element])
        while k > 0:
            count, element = heapq.heappop(heap)
            if count > 1:
                heapq.heappush(heap, [count-1,element])
            k-=1
        return len(heap)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr, key=lambda x: (c[x], x))
        return len(set(s[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = collections.Counter(arr)
        count = 0
        for i in sorted(list(c.items()), key = lambda x: x[1]):
            # print(i)
            if k - i[1] >= 0:
                k -= i[1]
                count += 1
            elif k - i[1] < 0:
                break
        return len(c)-count
        
            
        


from heapq import heappop, heappush

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        freq_map = {}
        heap = []
        
        for elem in arr:
            if elem not in freq_map:
                freq_map[elem] = 0
                
            freq_map[elem] += 1
            
        
        
        for key in freq_map:
            heappush(heap,(freq_map[key],key))
            
        while k > 0:
            
            count, num = heappop(heap)
            k -= count
            
        return len(heap)+1 if k < 0 else len(heap)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        num_count = defaultdict(int)
        
        for i in arr:
            num_count[i] += 1
        
        h = []
        
        
        key_count = 0
        
        for key in list(num_count.keys()):
            heapq.heappush(h,(num_count[key],key))
            key_count += 1
    
        result = key_count
    
        while k > 0:
            count,num = heapq.heappop(h)
            k = k-count
            if k >= 0:
                result -= 1
                continue
            if k < 0:
                break
                
                
                
        return result
            
            
            
        
        
        
        


from collections import Counter

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        l = k
        if k == 0: l = -len(arr)
        L = [item for items, c in Counter(arr).most_common() for item in [items] * c][:-l]
        print(L)
        return len(set(L))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        l = {}
        for i in arr:
            if i in l:
                l[i] += 1
            else:
                l[i] = 1
        l = sorted(l.items(), key=lambda x: x[1])
        i = 0
        while k > 0:
            if l[i][1] <= k:
                k -= l[i][1]
            else:
                break
            i += 1
        return len(l) - i

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = sorted(collections.Counter(arr).items(), key=lambda x: x[1])
        c = 0
        for kk, v in count:
            if k >= v:
                k -= v
                c += 1
            else:
                break
        return len(count) - c

import heapq
from collections import defaultdict
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        dic = defaultdict(int)
        for i in arr:
            dic[i] += 1
        for i in dic:
            heapq.heappush(heap, (dic[i], i))
        print(heap)
        while k:
            top = heap[0]
            if top[0] > k:
                break
            else:
                k -= top[0]
                heapq.heappop(heap)
        return len(heap)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        di=collections.defaultdict(int)
        for v in arr:
            di[v]+=1
        ar=sorted([v for k,v in list(di.items())],reverse=True)
        while ar and k>=ar[-1]:
            k-=ar.pop()
        return len(ar)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        heap = []
        for key, val in collections.Counter(arr).items():
            heapq.heappush(heap, (val, key))
            
        for _ in range(k):
            val, key = heapq.heappop(heap)
            #val -= 1
            if val > 1:
                heapq.heappush(heap, (val - 1, key))
            
        return len(heap)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:

        # create a dictionary of {number: count}
        num_count_dict = {}
        for num in arr:
            if num in num_count_dict:
                num_count_dict[num] += 1
            else:
                num_count_dict[num] = 1
                
        # create a dictionary of {count: a_list_of_number}
        num_dict = {}
        for num in num_count_dict.keys():
            count = num_count_dict[num] 
            if count in num_dict:
                num_dict[count].append(num)
            else:
                num_dict[count] = [num]
        
        # sorted num_dict by each number's count
        sorted_num_by_count = sorted(num_count_dict.items(), key=lambda x: x[1])
        #print(sorted_num_by_count)
        
        # remove number of the list
        for i in range (0, len(sorted_num_by_count)):
            num = sorted_num_by_count[i][0] # get dict key
            #print('num={}, k={}, num_count_dict={}'.format(num, k, num_count_dict[num]))
            num_count = num_count_dict[num]
            if num_count <= k:
                del num_count_dict[num]
            else:
                num_count_dict[num] = num_count_dict[num]-k
            k = k-num_count
            if k == 0:
                break
        return len(num_count_dict)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        s = sorted(arr, key = lambda x:(c[x], x))
        return len(set(s[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = collections.Counter(arr)
        ans = len(c)
        for v in sorted(c.values()):
            if v <= k:
                ans -= 1
                k -= v
        return ans

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        import heapq
        heap = []
        temp = {}
        for i in arr:
            if i in temp:
                temp[i] +=1
            else:
                temp[i] =1
        
        for key in temp:
            heapq.heappush(heap, (temp[key], key ))
       
    
        print(heap)
        
        while (heap and k):
            count ,key = heapq.heappop(heap)
            print((count , key , k))
            if k >= count:
                k -=count
            else:
                return len(heap) +1
        return len(heap)
    
# class Solution(object):
#     def findLeastNumOfUniqueInts(self, arr, k):
#         heap = []
#         count = collections.Counter(arr)
#         for key in count:
#             heapq.heappush(heap, (count[key], key))
        
#         while(heap and k):
#             count, key = heapq.heappop(heap)
#             if k >= count:
#                 k -= count
#             else:
#                 return len(heap) + 1
#         return len(heap)


from typing import List
from collections import Counter
import heapq
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        element_count = Counter(arr)
        count_heap = []
        for element, count in element_count.most_common():
            heapq.heappush(count_heap, [count, element])
        
        while k > 0:
            curr_count, curr_elem = heapq.heappop(count_heap)
            if k < curr_count:
                curr_count -= k
                k = 0
                heapq.heappush(count_heap, [curr_count, curr_elem])
            elif k > curr_count:
                k -= curr_count
            else:
                k = 0
        

        return len(count_heap)

import heapq 
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        dictv = {}
        li = []
        for i in arr:
            if i in dictv:
                dictv[i] +=1
            else:
                dictv[i] = 1
        
        li = []
        for i in dictv:
            heapq.heappush(li,(dictv[i], i))
            
        for _ in range(k):
            val, key = heapq.heappop(li)
            if val > 1:
                heapq.heappush(li, (val - 1, key))
        return len(li)


from typing import List
from heapq import *

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        hashmap = {}
        def insert(num):
            if num in hashmap:
                hashmap[num] += 1
            else:
                hashmap[num] = 1

        for num in arr:
            insert(num)

        valkeys = [ (hashmap[key], key) for key in list(hashmap.keys()) ] 

        kSmallest = nsmallest(k, valkeys)
        uniqueCount = len(valkeys)
        removals = k

        for (occ, num) in kSmallest:
            if (removals - occ) >= 0:
                removals -= occ
                uniqueCount -= 1
            else:
                break

        return uniqueCount




            



class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        sarr = sorted(arr, key = lambda x: (c[x], x))
        return len(set(sarr[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        count = collections.Counter(arr)
        pq = [(val, key) for key, val in list(count.items())]
        heapq.heapify(pq)
        
        while pq and k>0:
            freq, val = heapq.heappop(pq)
            if freq <= k:
                k -= freq
            else:
                heapq.heappush(pq, (freq-k, val))
                k = 0
                
        return len(pq)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        from collections import Counter
        from heapq import heappush,heappop
        d=Counter(arr)
        q=[]
        
        for ele in d:
            
            heappush(q,[d[ele],ele])
        print(q)   
        for i in range(k):
            temp=q[0]
            if temp[0]==1:
                print(temp)
                heappop(q)
            else:
                temp[0]-=1
        return len( q)


class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnts = collections.Counter(arr)
        heap = [(v, k) for k, v in cnts.items()]
        heapq.heapify(heap)
        for _ in range(k):
            cnt, val = heapq.heappop(heap)
            cnt -= 1
            if cnt != 0:
                heapq.heappush(heap, (cnt, val))
        return len(heap)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        c = Counter(arr)
        s = sorted(arr,key = lambda x:(c[x],x))
        print(s)
        return len(set(s[k:]))

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = collections.defaultdict(int)
        
        for num in arr:
            cnt[num] += 1
            
        a = [(cnt[key], key) for key in cnt]
        a.sort(key = lambda x:x[0])
        
        ret = len(a)
        
        i = 0
        while k:
            if a[i][0] <= k:
                k -= a[i][0]
                ret -= 1
                
            else:
                break
                
            i += 1
            
        return ret