• Time:Time:
• Space:Space:

## C++

``````class Solution {
public:
int minSetSize(vector<int>& arr) {
const int n = arr.size();
int sum = 0;
unordered_map<int, int> map;
vector<pair<int, int>> count;

for (const int a : arr)
++map[a];

for (const auto& [a, freq] : map)
count.push_back(make_pair(a, freq));

sort(begin(count), end(count),
[](const auto& a, const auto& b) { return a.second > b.second; });

for (int i = 0; i < count.size(); ++i) {
sum += count[i].second;
if (sum >= n / 2)
return i + 1;
}

throw;
}
};
``````

## JAVA

``````class Solution {
public int minSetSize(int[] arr) {
final int n = arr.length;
int sum = 0;
Map<Integer, Integer> map = new HashMap<>();

for (final int a : arr)
map.merge(a, 1, Integer::sum);

int[][] count = new int[map.size()][2];
int i = 0;

for (final int key : map.keySet()) {
count[i][0] = key;
count[i++][1] = map.get(key);
}

Arrays.sort(count, (c1, c2) -> c2[1] - c1[1]);

for (i = 0; i < count.length; ++i) {
sum += count[i][1];
if (sum >= n / 2)
return i + 1;
}

throw new IllegalArgumentException();
}
}
``````

## Python

``````class Solution:
def minSetSize(self, arr: List[int]) -> int:
n = len(arr)

count = Counter(arr).most_common()
count.sort(key=lambda c: -c[1])

sum = 0
for i, c in enumerate(count):
sum += c[1]
if sum >= n // 2:
return i + 1
``````