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.length is even.1 <= arr[i] <= 105This 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.
The code defines a function minSetSize that calculates the minimum set size required to remove at least half of the integers in the array. It uses an array to count the frequency of each element, sorts this frequency array, and removes elements starting with the most frequent to fulfill the condition. The function returns the size of the set needed.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
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.
This C code implements a bucket-based frequency count. It populates a bucket array where the index represents frequency and the value represents how many numbers have that frequency. By accessing these buckets from highest to lowest, we efficiently calculate the number of elements we need to remove from the array to reach at least half its size.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) because of bucket sorting.
Space Complexity: O(n) due to auxiliary arrays.
| Approach | Complexity |
|---|---|
| Sort by Frequency | Time Complexity: O(n log n) due to sorting. |
| Bucket Sort for Frequency Count | Time Complexity: O(n) because of bucket sorting. |
Leetcode 1338. Reduce Array Size to The Half • Fraz • 10,152 views views
Watch 9 more video solutions →Practice Reduce Array Size to The Half with our built-in code editor and test cases.
Practice on FleetCode