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

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Mathematics

Greedy algorithms

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

Solutions:
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:
				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:
		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
		queue = [(nums[i], i) for i in nums]
		heapq.heapify(queue)
		while len(queue) > 0 and k > 0:
			(count, n) = heapq.heappop(queue)
			if k >= count:
				k = k - count
			else:
				count = count - k
				k = 0
				heapq.heappush(queue, (count, n))
		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


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:
		num_count_dict = {}
		for num in arr:
			if num in num_count_dict:
				num_count_dict[num] += 1
			else:
				num_count_dict[num] = 1
		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_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]
			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:
		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])
		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
		return count


from collections import Counter

class Solution:

	def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
		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)


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


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)
			elif len(minHeap) == 1:
				minHeap[0][0] -= k
				k = 0
			else:
				k = 0
		return len(minHeap)


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]))
		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)
		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)
		for i in range(n_unique):
			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]))
		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
		records = {}
		q = []
		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)


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:
		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
		arrcounts = collections.Counter(arr)
		arrcounts = sorted(arrcounts.items(), key=lambda x: x[1])
		i = k
		j = 0
		while i > 0 and j < len(arrcounts):
			i -= arrcounts[j][1]
			if i >= 0:
				arrcounts.pop(j)
			else:
				j += 1
		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:
		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:
		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]
			freq = val[1]
			k -= freq
			if k >= 0:
				counted_arr.pop(0)
		return len(counted_arr)


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:
				return remaining - k // 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
		dictionary = {key: value for (key, value) in sorted(dictionary.items(), key=lambda item: item[1])}
		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
			numLettersToRemove -= 1
		outputList = keyList[keyPointer:]
		output = outputList.__len__()
		return output


class Solution:

	def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
		H = dict()
		for element in arr:
			if element in H:
				H[element] += 1
			else:
				H[element] = 1
		H = {k: v for (k, v) in sorted(list(H.items()), key=lambda item: item[1])}
		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:
			if k >= i[1]:
				k -= i[1]
				size -= 1
		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:
		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:
		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)


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:
		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()
				result -= 1
				k -= i
		return result


from collections import Counter

class Solution:

	def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
		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:
		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:

	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:
		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)
		return len(hp) + (k < 0)


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:]))


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
		counter = Counter(arr)
		counter = sorted(counter.most_common(), key=lambda x: (x[1], x[0]), reverse=True)
		while k > 0 and counter:
			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))


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:
		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 = collections.Counter(arr)
		count = 0
		for i in sorted(list(c.items()), key=lambda x: x[1]):
			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:
		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)


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:
		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:
		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