Reduce Array Size to The Half solution and explanation
9 more videos on this problem
1338 . Reduce Array Size to The Half Leetcode || Medium || July Daily ChallengeCode with Alisha · 8:45 · 4K views
Reduce Array Size to The Half | Leetcode 1338 | Live coding sessionCoding Decoded · 9:29 · 3K views
Leetcode - Reduce Array Size to The Half (Python)Timothy H Chang · 3:09 · 1K views
1338. Reduce Array Size to The Half | LEETCODE MEDIUM | GREEDY | BITS PILANIcode Explainer · 5:28 · 1K views
Reduce Array Size to the Half (LeetCode) | Interview Question ExplainedJyotinder Singh · 8:15 · 911 views
Reduce Array Size to the Half (Java) | Leetcode 1338 | July Coding Challenge Day 6Puru Arora · 8:17 · 678 views
Reduce Array Size to The Half (Leetcode 1338)Coding Interviews · 10:26 · 647 views
Reduce Array Size to The Half | LeetCode 1338 | Coders CampCoders Camp · 7:18 · 609 views
Daily Leetcode #870: Aug 18, 2022 - 1338. Reduce Array Size to The HalfProgramming Live with Larry · 4:43 · 318 views
1338. Reduce Array Size to The HalfTech Adora by Nivedita · 5:37 · 268 views
The problem
You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.
Example 1:
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has a size greater than half of the size of the old array.
Example 2:
Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.
Constraints:
2 <= arr.length <= 105arr.lengthis even.1 <= arr[i] <= 105
Approach overview
Problem Overview: You are given an integer array and must remove all occurrences of some chosen values. The goal is to pick the smallest number of unique integers such that removing them deletes at least half of the array elements. The challenge is deciding which values to remove first to minimize the set size.
Approach 1: Sort by Frequency (Greedy) (Time: O(n log n), Space: O(n))
Start by counting how often each number appears using a hash table. Each frequency tells you how many elements disappear if that value is removed. The greedy insight is simple: always remove the most frequent values first because they shrink the array fastest. After building the frequency map, place the counts into a list and sort them in descending order using sorting. Iterate through the sorted frequencies, subtracting them from the remaining array size until at least n / 2 elements are removed. The number of frequencies used is the answer.
This approach is straightforward and works well for interviews because the logic is easy to explain. The dominant cost comes from sorting the frequency list. If there are k unique numbers, sorting costs O(k log k), which is at most O(n log n) in the worst case.
Approach 2: Bucket Sort for Frequency Count (Time: O(n), Space: O(n))
You can avoid sorting by observing that frequencies are bounded by the array size. After counting occurrences with a hash table, create a bucket array where index i stores how many numbers appear exactly i times. This technique is a variation of bucket sorting often used for frequency-based greedy problems.
Iterate through the bucket array from highest frequency to lowest. Each step represents choosing numbers that remove many elements at once. Subtract frequency × count_of_numbers from the remaining elements until at least half of the array is removed. Because each element contributes to exactly one bucket and you scan the bucket array once, the total time complexity stays O(n). This makes it faster than sorting for very large arrays.
The bucket strategy relies on the same greedy idea: prioritize values that remove the most elements. The difference is how the frequencies are processed. Instead of sorting them, the algorithm groups them by frequency and walks from largest to smallest.
Recommended for interviews: The greedy frequency approach with sorting is usually the expected answer. It clearly demonstrates the key idea—remove the most frequent numbers first—and is easy to implement in any language. The bucket-based solution shows deeper optimization skills by reducing the complexity to O(n), which can impress interviewers when you discuss performance improvements.
Approach 1: Sort by Frequency
This approach involves sorting the elements of the array based on their frequency. We start by counting the frequency of each element. Next, we create a list of these frequencies sorted in decreasing order. By selecting the most frequent elements first, we remove them from the array until at least half of the array size is removed.
from collections import Counter
def minSetSize(arr):
frequency = Counter(arr)
freq_values = sorted(frequency.values(), reverse=True)
removed = 0
set_size = 0
half_size = len(arr) // 2
for freq in freq_values:
removed += freq
set_size += 1
if removed >= half_size:
break
return set_size
arr = [3,3,3,3,5,5,5,2,2,7]
print(minSetSize(arr))import java.util.*;
public class ReduceArraySize {
public static int minSetSize(int[] arr) {
Map<Integer, Integer> frequency = new HashMap<>();
for (int num : arr) {
frequency.put(num, frequency.getOrDefault(num, 0) + 1);
}
List<Integer> frequencies = new ArrayList<>(frequency.values());
frequencies.sort(Collections.reverseOrder());
int removed = 0, setSize = 0, halfSize = arr.length / 2;
for (int freq : frequencies) {
removed += freq;
setSize++;
if (removed >= halfSize) {
break;
}
}
return setSize;
}
public static void main(String[] args) {
int[] arr = {3,3,3,3,5,5,5,2,2,7};
System.out.println(minSetSize(arr));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
int minSetSize(vector<int>& arr) {
unordered_map<int, int> frequency;
for (int num : arr) {
frequency[num]++;
}
vector<int> freqValues;
for (auto& pair : frequency) {
freqValues.push_back(pair.second);
}
sort(freqValues.rbegin(), freqValues.rend());
int removed = 0, setSize = 0;
for (int freq : freqValues) {
removed += freq;
setSize++;
if (removed >= arr.size() / 2) {
break;
}
}
return setSize;
}
int main() {
vector<int> arr = {3,3,3,3,5,5,5,2,2,7};
cout << minSetSize(arr) << endl;
return 0;
}function minSetSize(arr) {
const frequency = {};
arr.forEach(num => {
frequency[num] = (frequency[num] || 0) + 1;
});
const freqValues = Object.values(frequency).sort((a, b) => b - a);
let removed = 0, setSize = 0, halfSize = arr.length / 2;
for (const freq of freqValues) {
removed += freq;
setSize++;
if (removed >= halfSize) {
break;
}
}
return setSize;
}
console.log(minSetSize([3,3,3,3,5,5,5,2,2,7]));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return *(int*)b - *(int*)a;
}
int minSetSize(int* arr, int arrSize) {
int frequency[100001] = {0};
for (int i = 0; i < arrSize; i++) {
frequency[arr[i]]++;
}
int freqCount[100001] = {0};
int freqSize = 0;
for (int i = 0; i < 100001; i++) {
if (frequency[i] > 0) {
freqCount[freqSize++] = frequency[i];
}
}
qsort(freqCount, freqSize, sizeof(int), compare);
int sum = 0, setSize = 0;
for (int i = 0; i < freqSize; i++) {
sum += freqCount[i];
setSize++;
if (sum >= arrSize / 2) {
return setSize;
}
}
return setSize;
}
int main() {
int arr[] = {3,3,3,3,5,5,5,2,2,7};
int arrSize = sizeof(arr)/sizeof(arr[0]);
printf("%d\n", minSetSize(arr, arrSize));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int MinSetSize(int[] arr) {
var frequency = new Dictionary<int, int>();
foreach (var num in arr) {
if (frequency.ContainsKey(num))
frequency[num]++;
else
frequency[num] = 1;
}
var freqList = frequency.Values.OrderByDescending(x => x).ToList();
int removed = 0, setSize = 0, halfSize = arr.Length / 2;
foreach (var freq in freqList) {
removed += freq;
setSize++;
if (removed >= halfSize) break;
}
return setSize;
}
public static void Main(string[] args) {
int[] arr = {3,3,3,3,5,5,5,2,2,7};
Solution sol = new Solution();
Console.WriteLine(sol.MinSetSize(arr));
}
}The Python solution employs the Counter class from the collections module to map each element to its frequency. These frequencies are sorted in descending order, and the program computes the minimal set size required to remove half of the integers in the array by iteratively subtracting from the sorted frequency list.
Time Complexity: O(n log n) for sorting the frequency list.
Space Complexity: O(n) due to the counting of elements.
Approach 2: Bucket Sort for Frequency Count
This approach utilizes bucket sort, where frequencies are counted and used as indices in a bucket array to represent how many numbers occur with identical frequency. This helps in efficiently choosing elements to remove, optimizing beyond traditional sorting by directly accessing through indices.
from collections import Counter
def minSetSize(arr):
frequency = Counter(arr)
bucket = [0] * (len(arr) + 1)
for freq in frequency.values():
bucket[freq] += 1
removed = setSize = 0
halfSize = len(arr) // 2
for i in range(len(arr), 0, -1):
while bucket[i] > 0:
removed += i
setSize += 1
bucket[i] -= 1
if removed >= halfSize:
return setSize
arr = [3,3,3,3,5,5,5,2,2,7]
print(minSetSize(arr))import java.util.*;
public class ReduceArraySize {
public static int minSetSize(int[] arr) {
Map<Integer, Integer> frequency = new HashMap<>();
for (int num : arr) {
frequency.put(num, frequency.getOrDefault(num, 0) + 1);
}
int[] bucket = new int[arr.length + 1];
for (int freq : frequency.values()) {
bucket[freq]++;
}
int removed = 0, setSize = 0, halfSize = arr.length / 2;
for (int i = arr.length; i > 0; i--) {
while (bucket[i] > 0) {
removed += i;
setSize++;
bucket[i]--;
if (removed >= halfSize) return setSize;
}
}
return setSize;
}
public static void main(String[] args) {
int[] arr = {3,3,3,3,5,5,5,2,2,7};
System.out.println(minSetSize(arr));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int minSetSize(vector<int>& arr) {
unordered_map<int, int> count;
for (int num : arr) count[num]++;
vector<int> bucket(arr.size() + 1, 0);
for (auto& pair : count) {
bucket[pair.second]++;
}
int halfSize = arr.size() / 2, removed = 0, setSize = 0;
for (int i = arr.size(); i > 0; i--) {
while (bucket[i] > 0) {
removed += i;
setSize++;
bucket[i]--;
if (removed >= halfSize) return setSize;
}
}
return setSize;
}
int main() {
vector<int> arr = {3,3,3,3,5,5,5,2,2,7};
cout << minSetSize(arr) << endl;
return 0;
}function minSetSize(arr) {
const frequency = {};
arr.forEach(num => {
frequency[num] = (frequency[num] || 0) + 1;
});
const bucket = new Array(arr.length + 1).fill(0);
Object.values(frequency).forEach(freq => {
bucket[freq]++;
});
let removed = 0, setSize = 0, halfSize = arr.length / 2;
for (let i = arr.length; i > 0; i--) {
while (bucket[i] > 0) {
removed += i;
setSize++;
if (removed >= halfSize) {
return setSize;
}
bucket[i]--;
}
}
return setSize;
}
console.log(minSetSize([3,3,3,3,5,5,5,2,2,7]));#include <stdio.h>
#include <stdlib.h>
int minSetSize(int* arr, int arrSize) {
int count[100001] = {0};
for (int i = 0; i < arrSize; i++) {
count[arr[i]]++;
}
int bucket[100001] = {0};
for (int i = 0; i <= 100000; i++) {
if (count[i] > 0) {
bucket[count[i]]++;
}
}
int halfSize = arrSize / 2, removed = 0, setSize = 0;
for (int i = 100000; i > 0; i--) {
while (bucket[i] > 0) {
removed += i;
setSize++;
bucket[i]--;
if (removed >= halfSize) {
return setSize;
}
}
}
return setSize;
}
int main() {
int arr[] = {3,3,3,3,5,5,5,2,2,7};
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("%d\n", minSetSize(arr, arrSize));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int MinSetSize(int[] arr) {
var frequency = new Dictionary<int, int>();
foreach (var num in arr) {
if (frequency.ContainsKey(num))
frequency[num]++;
else
frequency[num] = 1;
}
int[] bucket = new int[arr.Length + 1];
foreach (var freq in frequency.Values) {
bucket[freq]++;
}
int removed = 0, setSize = 0, halfSize = arr.Length / 2;
for (int i = arr.Length; i > 0; i--) {
while (bucket[i] > 0) {
removed += i;
setSize++;
bucket[i]--;
if (removed >= halfSize) return setSize;
}
}
return setSize;
}
public static void Main(string[] args) {
int[] arr = {3,3,3,3,5,5,5,2,2,7};
Solution sol = new Solution();
Console.WriteLine(sol.MinSetSize(arr));
}
}The Python solution utilizes bucket sorting to store the count of elements with the same frequency in an array. Working from largest to smallest frequency, the code calculates the minimal integer set size necessary to remove at least half of the array. This approach bypasses common sorting algorithms, optimizing the frequency ordering task.
Time Complexity: O(n) through bucket allocation and iteration.
Space Complexity: O(n), primarily due to frequency and bucket storage.
Approach 3: Counting + Sorting
We can use a hash table or an array cnt to count the occurrences of each number in the array arr. Then, we sort the numbers in cnt in descending order. We traverse cnt from largest to smallest, adding the current number x to the answer and adding x to m. If m geq \frac{n}{2}, we return the answer.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array arr.
function minSetSize(arr: number[]): number {
const cnt = new Map<number, number>();
for (const v of arr) {
cnt.set(v, (cnt.get(v) ?? 0) + 1);
}
let [ans, m] = [0, 0];
for (const v of Array.from(cnt.values()).sort((a, b) => b - a)) {
m += v;
++ans;
if (m * 2 >= arr.length) {
break;
}
}
return ans;
}func minSetSize(arr []int) (ans int) {
mx := slices.Max(arr)
cnt := make([]int, mx+1)
for _, x := range arr {
cnt[x]++
}
sort.Ints(cnt)
for i, m := mx, 0; ; i-- {
if cnt[i] > 0 {
m += cnt[i]
ans++
if m >= len(arr)/2 {
return
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort by Frequency | Time Complexity: O(n log n) for sorting the frequency list. |
| Bucket Sort for Frequency Count | Time Complexity: O(n) through bucket allocation and iteration. |
| Counting + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort by Frequency (Greedy) | O(n log n) | O(n) | General interview solution. Simple implementation using hash map and sorting. |
| Bucket Sort for Frequency Count | O(n) | O(n) | When optimizing beyond sorting. Useful when array size is large and frequency bounds allow bucket grouping. |
Frequently asked questions
Is Reduce Array Size to The Half easy or hard?
The problem is rated Medium because the greedy idea is simple but recognizing that you should remove the highest-frequency numbers first requires insight. Efficient implementations also involve hash maps and optional bucket optimization.
Reduce Array Size to The Half Python/Java solution
In Python or Java, the typical solution counts frequencies using a dictionary or HashMap, collects the counts into a list, sorts them in descending order, and keeps removing the largest counts until at least half of the array elements are removed.
How to solve Reduce Array Size to The Half in O(n)?
Use a bucket sort approach on element frequencies. After building a hash map of counts, store how many numbers appear with each frequency in a bucket array. Traverse the buckets from highest frequency to lowest while removing elements until at least half of the array is deleted. This avoids sorting and runs in O(n) time.
What is the best approach for Reduce Array Size to The Half?
The best approach uses a greedy strategy based on element frequency. Count occurrences with a hash map, then remove numbers with the highest frequencies first. Sorting the frequencies gives an O(n log n) solution, while a bucket-based frequency approach can improve it to O(n).
Is Reduce Array Size to The Half asked at Google/Amazon/Meta?
Frequency-based greedy problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. The question tests hash map usage, greedy decision making, and the ability to optimize frequency processing with sorting or buckets.
What data structure is used in Reduce Array Size to The Half?
The core data structure is a hash table (or dictionary) used to count how many times each number appears. Many implementations also use arrays or priority queues to process the frequencies in descending order.
What is the time complexity of Reduce Array Size to The Half?
The common greedy solution runs in O(n log n) time because it sorts the frequency counts of unique elements. With bucket sort on frequencies, the complexity improves to O(n) since each element and frequency bucket is processed once.