1481. Least Number of Unique Integers after K Removals

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        """
        1. cnt 
        2. sort by occurance, delete least occurance with k  
        3. return len(d) + (k < 0 )
        O(NlgN)  space O(N)
        """
        d = {} 
        for num in arr:
            d[num] = d.get(num,0) + 1 
        kv = sorted(list(d.items()),key = lambda k : k[1])
        i = 0
        
        while k > 0:
            k = k - kv[i][1]
            i += 1 
        return len(kv)-i + (k<0)

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        """
        main idea: cnt + bucket sort
        1.
        2. sort by occurance, delete least occurance with k  
        3. return len(d) + (k < 0 )
        O(NlgN)  space O(N)
        """
        d = {} 
        for num in arr:
            d[num] = d.get(num,0) + 1
        #print(d)
        cnt = [0]*(len(arr)+1)
        
        for _,v in d.items():
            cnt[v] += 1 
        
        i = 1
       # print(cnt)
        while k > 0:
            if cnt[i] > 0:
                k = k - i
                cnt[i] -= 1
            else:
                i += 1 
        return sum(cnt) + (k<0)
        

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        """
        main idea: cnt + bucket sort
        1. count occurance, initialize bucket sort value based on occurance
        2. go through bucket, substract number of value at same occurance within valid k 
        3. return  remaining unique values
        O(N)  space O(N)
        """
        d = {} 
        for num in arr:
            d[num] = d.get(num,0) + 1
        cnt = [0]*(len(arr)+1)
        
        for v in d.values():
            cnt[v] += 1 
        remain = len(d)
        
        for i in range(1,len(cnt)):
            if k - i * cnt[i] >= 0:
                k = k - i * cnt[i]
                remain -= cnt[i]
            else:
                return remain - k// i
                
        return remain