Reduce Array Size to The Half

Reduce Array Size to The Half

What is this problem about?

The Reduce Array Size to The Half problem asks for the minimum number of unique integer values to remove such that the remaining array is at most half the original size. This coding problem uses frequency-based greedy selection — remove the most frequent elements first. The array, hash table, sorting, heap, and greedy interview pattern is the core.

Why is this asked in interviews?

Akuna Capital and Meta ask this because greedy selection by frequency is the optimal strategy: removing the most frequent element removes the most occurrences per "slot" used. It validates understanding of the greedy optimality proof.

Algorithmic pattern used

Frequency sort + greedy greedy selection. Count frequencies of all values. Sort frequencies in descending order. Greedily remove the most frequent values first, accumulating the count of removed elements. Stop when removed ≥ n/2.

Example explanation

arr=[3,3,3,3,5,5,5,2,2,7,1,1,1,4,1,6]. n=16. Target remove ≥ 8. Frequencies: {3:4, 5:3, 1:4, 2:2, 7:1, 4:1, 6:1}. Sorted desc: [4,4,3,2,1,1,1].

• Remove 3 (freq 4): count=4. Need 4 more.
• Remove 1 (freq 4): count=8 ≥ 8. Total removed = 2 unique values.

Common mistakes candidates make

• Sorting by frequency ascending instead of descending.
• Off-by-one in target: must reduce to AT MOST n/2, so remove ≥ ceil(n/2).
• Not counting the unique values removed (counting total elements removed instead).
• Using a min-heap instead of max-heap or sorted desc list.

Interview preparation tip

Reduce Array Size to The Half is a straightforward greedy: remove most frequent first. The proof of optimality: any other ordering removes fewer total elements per unique value used. Practice similar "minimum removals to satisfy size constraint" problems. The max-heap or sorted-desc frequency approach is the standard solution.