Reduce Array Size to The Half
Medium · Greedy · Array · Hash Table · Greedy · Sorting · Heap (Priority Queue)
Problem
You are given an integer array arr of even length. You may choose a set of distinct values and remove every occurrence of each chosen value from the array.
Return the smallest possible size of the chosen set such that at least half of the array's elements are removed.
Examples
Input: arr = [4,4,4,4,1,2,3,5] Output: 1
Removing all the 4s deletes 4 of the 8 elements.
Input: arr = [1,2,3,4,5,6] Output: 3
Each value removes one element, and three must go.
Input: arr = [9,9,8,8,7,7,6,6] Output: 2
Each value removes two elements, and four removals are needed.
Constraints
- 2 <= len(arr) <= 10^5
- len(arr) is even
- 1 <= arr[i] <= 10^5
Approaches
- Baseline: scan for the largest count each time — time O(n + k · d), space O(d)
Follow-up
Every chosen value costs one, so the most frequent value is always the best next choice, and swapping any chosen value for a more frequent one never hurts. The use cases change the goal: remove exactly k elements while keeping few distinct values (now the rarest go first), and halve the sum instead of the length (rank by value times count).
Related problems
Start free on Cariara · Coding problems · System design studio
