Reduce Array Size to The Half

Med

#1243Time: O(N log N). Counting frequencies takes O(N). If there are U unique elements, sorting their frequencies takes O(U log U). In the worst case, U can be equal to N, leading to a time complexity of O(N + N log N) which simplifies to O(N log N).Space: O(N). The `HashMap` can store up to N unique elements, and the list of frequencies can also have a size of up to N in the worst case where all elements are unique.1 company

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Hash Table Heap (Priority Queue)

Companies

Akuna Capital

Prompt

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 <= 10⁵
arr.length is even.
1 <= arr[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

The core idea is to be greedy. To remove at least half the elements using the minimum number of distinct integers, we should prioritize removing the integers that appear most frequently. This approach first calculates the frequency of each number, then sorts these frequencies in descending order, and finally iterates through the sorted frequencies, adding them up until the total number of removed elements reaches the target.

Algorithm

Create a HashMap<Integer, Integer> to store the frequency of each number.
Iterate through the input array arr and populate the frequency map.
Extract the values (frequencies) from the map into a List<Integer>.
Sort the list of frequencies in descending order.
Initialize removedCount = 0, setSize = 0, and target = arr.length / 2.
Iterate through the sorted frequencies from largest to smallest.
For each frequency, add it to removedCount and increment setSize.
If removedCount becomes greater than or equal to target, return setSize.

Walkthrough

We start by counting how many times each number appears in the input array arr. A HashMap is a suitable data structure for this, mapping each number to its frequency. Once we have all the frequencies, we don't need the numbers themselves anymore. We extract these frequencies into a list. To implement our greedy strategy, we sort this list of frequencies in descending order. Finally, we iterate through the sorted frequencies. We maintain a running sum of removed elements (removedCount) and a count of the distinct integers we've chosen to remove (setSize). In each step, we take the next largest frequency, add it to removedCount, and increment setSize. We stop as soon as removedCount is at least half the original array's size. The value of setSize at this point is our answer.

1import java.util.*;2 3class Solution {4    public int minSetSize(int[] arr) {5        Map<Integer, Integer> counts = new HashMap<>();6        for (int num : arr) {7            counts.put(num, counts.getOrDefault(num, 0) + 1);8        }9 10        List<Integer> frequencies = new ArrayList<>(counts.values());11        Collections.sort(frequencies, Collections.reverseOrder());12 13        int removedCount = 0;14        int setSize = 0;15        int target = arr.length / 2;16 17        for (int freq : frequencies) {18            removedCount += freq;19            setSize++;20            if (removedCount >= target) {21                break;22            }23        }24        return setSize;25    }26}

Complexity

Time

O(N log N). Counting frequencies takes O(N). If there are U unique elements, sorting their frequencies takes O(U log U). In the worst case, U can be equal to N, leading to a time complexity of O(N + N log N) which simplifies to O(N log N).

Space

O(N). The `HashMap` can store up to N unique elements, and the list of frequencies can also have a size of up to N in the worst case where all elements are unique.

Trade-offs

Pros

Intuitive and relatively straightforward to implement.
The logic directly follows the greedy strategy.

Cons

The comparison-based sort of frequencies has a time complexity of O(U log U), where U is the number of unique elements. This is the bottleneck and can be improved.

This approach optimizes the previous one by avoiding a comparison-based sort. After counting the frequencies of each number, we can use a technique similar to Bucket Sort. Since the frequencies are integers ranging from 1 to N (the length of the array), we can use an array to group numbers by their frequency. This allows us to process the frequencies in descending order in linear time.

Algorithm

Create a HashMap<Integer, Integer> to store the frequency of each number.
Iterate through the input array arr and populate the frequency map.
Create a buckets array of size arr.length + 1.
Iterate through the values (frequencies) of the map. For each frequency f, increment buckets[f].
Initialize removedCount = 0, setSize = 0, and target = arr.length / 2.
Iterate through the buckets array from index arr.length down to 1. Let the current index be f.
If buckets[f] is greater than 0, it means there are buckets[f] numbers that appear f times.
For each of these buckets[f] numbers, add f to removedCount, increment setSize, and check if removedCount >= target.
If the target is reached, return the current setSize.

Walkthrough

Similar to the first approach, we begin by counting the frequency of each number using a HashMap. The key optimization is what we do next. Instead of sorting the frequencies, we create a 'bucket' array. Let's call it buckets, of size n + 1, where n is the length of the input array. We iterate through the frequencies we calculated. For each frequency f, we increment buckets[f]. This means buckets[f] will store the count of numbers that appear f times in the original array. Now, to greedily pick the highest frequencies, we iterate through the buckets array backwards, from n down to 1. For each frequency f, we know that there are buckets[f] numbers we can remove, each contributing f to our removed count. We process these numbers one by one, updating our removedCount and setSize, until we reach the target of removing at least n / 2 elements. This avoids the O(N log N) sorting step, leading to a linear time solution.

1import java.util.*;2 3class Solution {4    public int minSetSize(int[] arr) {5        Map<Integer, Integer> counts = new HashMap<>();6        for (int num : arr) {7            counts.put(num, counts.getOrDefault(num, 0) + 1);8        }9 10        int n = arr.length;11        int[] buckets = new int[n + 1];12        for (int freq : counts.values()) {13            buckets[freq]++;14        }15 16        int removedCount = 0;17        int setSize = 0;18        int target = n / 2;19 20        for (int freq = n; freq >= 1; freq--) {21            if (buckets[freq] > 0) {22                int numCountWithThisFreq = buckets[freq];23                for (int i = 0; i < numCountWithThisFreq; i++) {24                    removedCount += freq;25                    setSize++;26                    if (removedCount >= target) {27                        return setSize;28                    }29                }30            }31        }32        return setSize; // Should not be reached33    }34}

Complexity

Time

O(N). Counting frequencies takes O(N). Populating the buckets array takes O(U) where U is the number of unique elements (U <= N). Iterating through the buckets takes O(N). The total time complexity is O(N + U + N) which simplifies to O(N).

Space

O(N). The `HashMap` can take up to O(U) space where U is the number of unique elements. The `buckets` array takes O(N) space. The total space complexity is O(U + N), which simplifies to O(N).

Trade-offs

Pros

Achieves optimal linear time complexity, O(N).
Efficiently 'sorts' frequencies without a comparison-based algorithm.

Cons

Uses extra space for the buckets array, which can be up to size N+1.
The logic is slightly more complex than the sorting approach.

Solutions

Solution

1class Solution {2public3  int minSetSize(int[] arr) {4    int mx = 0;5    for (int x : arr) {6      mx = Math.max(mx, x);7    }8    int[] cnt = new int[mx + 1];9    for (int x : arr) {10      ++cnt[x];11    }12    Arrays.sort(cnt);13    int ans = 0;14    int m = 0;15    for (int i = mx;; --i) {16      if (cnt[i] > 0) {17        m += cnt[i];18        ++ans;19        if (m * 2 >= arr.length) {20          return ans;21        }22      }23    }24  }25}

1class Solution {2public:3  int minSetSize(vector<int> &arr) {4    int mx = *max_element(arr.begin(), arr.end());5    int cnt[mx + 1];6    memset(cnt, 0, sizeof(cnt));7    for (int &x : arr) {8      ++cnt[x];9    }10    sort(cnt, cnt + mx + 1, greater<int>());11    int ans = 0;12    int m = 0;13    for (int &x : cnt) {14      if (x) {15        m += x;16        ++ans;17        if (m * 2 >= arr.size()) {18          break;19        }20      }21    }22    return ans;23  }24};

1class Solution:2    def minSetSize(self, arr: List[int]) -> int: cnt = Counter(arr) ans = m = 0 for _, v in cnt . most_common(): m += v ans += 1 if m * 2 >= len(arr): break return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem