Reduce Array Size to The Half Solution

Problem

You have an array of integers and want to remove all occurrences of chosen integers until the array is at most half its original length. Find the minimum number of distinct integers you need to choose.

For example, in arr = [3,3,3,3,5,5,5,2,2,7]:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3, 5} removes 4 + 3 = 7 entries, leaving [2,2,7] with length 3, which is ≤ 5.

Note that choosing {3, 7} also removes exactly 5 entries (just enough), but choosing only {3} removes just 4 — not sufficient.

Intuition

Each integer you choose to remove eliminates all of its occurrences at once. To minimize how many integers you choose, you should always grab the most frequent one next — it delivers the most removed entries per pick. Any swap of a high-frequency choice for a lower-frequency one forces you to use more picks to reach the target. This greedy strategy is provably optimal.

Approach 1 — Greedy + Sort

Count how often each integer appears, sort those counts descending, then accumulate until you've eliminated at least half the array.

Build a frequency map of every integer in the array.
Extract the frequency values and sort them descending.
Walk through sorted frequencies, adding each to a running removed total.
The first moment removed >= target, return how many frequencies you consumed.

1from collections import Counter
2
3def minSetSize(arr: list[int]) -> int:
4    freq_map = Counter(arr)
5    # Sort frequency values descending — always pick the highest count first
6    sorted_freqs = sorted(freq_map.values(), reverse=True)
7
8    target = len(arr) // 2
9    removed = 0
10    for num_chosen, freq in enumerate(sorted_freqs, 1):
11        removed += freq
12        if removed >= target:
13            return num_chosen
14    return len(sorted_freqs)

Time: O(n log n) — frequency map is O(n); sorting at most n distinct frequency values costs O(n log n).
Space: O(n) — the frequency map holds at most n entries.

Approach 2 — Greedy + Bucket Sort

The maximum frequency any element can have is n, so we can replace the comparison sort with a bucket array indexed by frequency and scan from high to low. This brings the overall time down to O(n).

Count element frequencies with a hash map.
Build a bucket array of size n + 1 where bucket[f] is the number of distinct integers that appear exactly f times.
Scan the bucket from index n down to 1, greedily draining each level until the removed total reaches the target.

1def minSetSize(arr: list[int]) -> int:
2    n = len(arr)
3    freq_map: dict[int, int] = {}
4    for num in arr:
5        freq_map[num] = freq_map.get(num, 0) + 1
6
7    # Index is frequency; value is how many distinct integers share that frequency
8    bucket = [0] * (n + 1)
9    for f in freq_map.values():
10        bucket[f] += 1
11
12    target = n // 2
13    removed = 0
14    num_chosen = 0
15    for f in range(n, 0, -1):
16        # Drain all elements at this frequency level before moving to a lower one
17        while bucket[f] > 0 and removed < target:
18            removed += f
19            num_chosen += 1
20            bucket[f] -= 1
21        if removed >= target:
22            return num_chosen
23    return num_chosen

Time: O(n) — frequency counting is O(n); the bucket array is size n + 1; the two-level scan visits at most n elements total.
Space: O(n) — frequency map and bucket array each use O(n).

Complexity Summary

Approach	Time	Space	When to use
Greedy + Sort	O(n log n)	O(n)	Clean and readable; fast enough for n ≤ 10^5
Greedy + Bucket Sort	O(n)	O(n)	When you need to prove linear time or squeeze out constants on very large inputs

Common Mistakes

Sorting frequencies in ascending order — picking the least frequent integers first means you exhaust small contributions before large ones, so you'll need many more picks to reach the target.
Using > target instead of >= target as the stopping condition — the problem says at least half, so reaching exactly target counts; stopping one step later wastes a pick.
Sorting the original array values instead of the frequency values — sorted values give you nothing directly; you need to count occurrences first, then sort those counts.
Incrementing num_chosen by the frequency instead of by 1 — each iteration you pick one distinct integer (which eliminates freq array entries); the answer is the count of distinct integers chosen, not total entries removed.
Sizing the bucket array by max(arr) + 1 instead of n + 1 — the bucket index represents frequency, which is bounded by n, not by the integer values themselves; max(arr) can be up to 10^5 and has nothing to do with how often an element appears.

Reduce Array Size to The Half — Solution