# Reduce Array Size to The Half
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/reduce-array-size-to-the-half)
Canonical: https://scaleengineer.com/dsa/problems/reduce-array-size-to-the-half
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table, Heap (Priority Queue)
**Companies:** [Akuna Capital](https://scaleengineer.com/companies/akuna-capital)
---
## 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 <= 105`
* `arr.length` is even.
* `1 <= arr[i] <= 105`

# Approaches
## Using Hash Map and Sorting
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.
**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.
**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.
### Explanation
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.
```java
import java.util.*;

class Solution {
    public int minSetSize(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : arr) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        List<Integer> frequencies = new ArrayList<>(counts.values());
        Collections.sort(frequencies, Collections.reverseOrder());

        int removedCount = 0;
        int setSize = 0;
        int target = arr.length / 2;

        for (int freq : frequencies) {
            removedCount += freq;
            setSize++;
            if (removedCount >= target) {
                break;
            }
        }
        return setSize;
    }
}
```
### 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`.

## Using Hash Map and Bucket Sort
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.
**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).
**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.
### Explanation
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.
```java
import java.util.*;

class Solution {
    public int minSetSize(int[] arr) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : arr) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        int n = arr.length;
        int[] buckets = new int[n + 1];
        for (int freq : counts.values()) {
            buckets[freq]++;
        }

        int removedCount = 0;
        int setSize = 0;
        int target = n / 2;

        for (int freq = n; freq >= 1; freq--) {
            if (buckets[freq] > 0) {
                int numCountWithThisFreq = buckets[freq];
                for (int i = 0; i < numCountWithThisFreq; i++) {
                    removedCount += freq;
                    setSize++;
                    if (removedCount >= target) {
                        return setSize;
                    }
                }
            }
        }
        return setSize; // Should not be reached
    }
}
```
### 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`.

# Solutions
### Java

```java
class Solution {
public
  int minSetSize(int[] arr) {
    int mx = 0;
    for (int x : arr) {
      mx = Math.max(mx, x);
    }
    int[] cnt = new int[mx + 1];
    for (int x : arr) {
      ++cnt[x];
    }
    Arrays.sort(cnt);
    int ans = 0;
    int m = 0;
    for (int i = mx;; --i) {
      if (cnt[i] > 0) {
        m += cnt[i];
        ++ans;
        if (m * 2 >= arr.length) {
          return ans;
        }
      }
    }
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minSetSize(vector<int> &arr) {
    int mx = *max_element(arr.begin(), arr.end());
    int cnt[mx + 1];
    memset(cnt, 0, sizeof(cnt));
    for (int &x : arr) {
      ++cnt[x];
    }
    sort(cnt, cnt + mx + 1, greater<int>());
    int ans = 0;
    int m = 0;
    for (int &x : cnt) {
      if (x) {
        m += x;
        ++ans;
        if (m * 2 >= arr.size()) {
          break;
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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

```