Reduce Array Size to The Half — Problem & Solution
Reduce Array Size to The Half solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Reduce Array Size to The Half is a medium coding problem on arrays, hash table and sorting, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Sorting, Greedy, Heap
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array arr. Choose a set of integers and remove every occurrence of them from arr.
Return the minimum size of such a set so that at least half of the array's elements are removed.
Example 1
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Removing {3,7} leaves 5 of the 10 elements.
Example 2
Input: arr = [7,7,7,7,7,7]
Output: 1
Example 3
Input: arr = [1,2]
Output: 1
Constraints
2 <= arr.length <= 40arr.length is even.1 <= arr[i] <= 100000
Hints for Reduce Array Size to The Half
Hint 1
Removing a value removes all of its copies at once, so only the frequencies matter.
Hint 2
Take the most frequent values first — each choice removes as much as possible.
Hint 3
Sort the frequencies descending and accumulate until the running total reaches half the length.
How to solve Reduce Array Size to The Half
Removing a value removes all its copies, so sort the frequencies descending and take the largest until at least half the array is gone.
Approach
- Count frequencies.
- Sort them descending and accumulate; stop when the total reaches
n / 2. - Return how many were taken.
Why it works
Each chosen value removes its full frequency; to reach the threshold with the fewest choices, take the largest frequencies first (exchange argument).
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
nis even by the constraints, son // 2is exact.
Reference solution
Python
def minSetSize(arr) -> int:
count = {}
for x in arr:
count[x] = count.get(x, 0) + 1
freqs = sorted(count.values(), reverse=True)
removed = chosen = 0
half = len(arr) // 2
for f in freqs:
removed += f
chosen += 1
if removed >= half:
break
return chosenJava
public static int minSetSize(int[] arr) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
List<Integer> freqs = new ArrayList<>(count.values());
Collections.sort(freqs, Collections.reverseOrder());
int removed = 0, chosen = 0;
int half = arr.length / 2;
for (int f : freqs) {
removed += f;
chosen++;
if (removed >= half) break;
}
return chosen;
}C++
int minSetSize(vector<int>& arr) {
unordered_map<int, int> count;
for (int x : arr) count[x]++;
vector<int> freqs;
for (const auto& kv : count) freqs.push_back(kv.second);
sort(freqs.begin(), freqs.end(), greater<int>());
int removed = 0, chosen = 0;
int half = (int) arr.size() / 2;
for (int f : freqs) {
removed += f;
chosen++;
if (removed >= half) break;
}
return chosen;
}JavaScript
var minSetSize = function(arr) {
const count = new Map();
for (let i = 0; i < arr.length; i++) {
count.set(arr[i], (count.get(arr[i]) || 0) + 1);
}
const freqs = [];
count.forEach(function(c) { freqs.push(c); });
freqs.sort(function(a, b) { return b - a; });
let removed = 0, chosen = 0;
const half = arr.length / 2;
for (let i = 0; i < freqs.length; i++) {
removed += freqs[i];
chosen++;
if (removed >= half) break;
}
return chosen;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets