<p>You are given an integer array <code>arr</code>. You can choose a set of integers and remove all the occurrences of these integers in the array.</p>

<p>Return <em>the minimum size of the set so that <strong>at least</strong> half of the integers of the array are removed</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [3,3,3,3,5,5,5,2,2,7]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [7,7,7,7,7,7]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only possible set you can choose is {7}. This will make the new array empty.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= arr.length &lt;= 10<sup>5</sup></code></li>
	<li><code>arr.length</code> is even.</li>
	<li><code>1 &lt;= arr[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public: /*  // Complexity: O(nlogn)     Space: O(n)
    int minSetSize(vector<int>& A) {
        int n = A.size(), res = 0;
        if (n <= 1)
            return n;
        if (n == 2)
            return 1;

        vector<int> uniqs;

        unordered_map<int, int> f;
        for (int num : A)
        {
            if (f[num]++ == 0)
                uniqs.push_back(num);
        }

        if (uniqs.size() == n)              // note: n+1/2
            return (n+1)/2;

        auto cmp = [&f](const int& i, const int& j) -> bool { return f[i] >= f[j]; };
        sort(uniqs.begin(), uniqs.end(), cmp);  // max

        for (int num : uniqs)
        {
            n -= f[num];
            res++;

            if (n <= A.size()/2)
                break;
        }
            
        return res;
    }                                                               */

    // Faster       Complexity: O(n) 
    int minSetSize(vector<int>& nums) {
        int n = nums.size(), res = 0, maxf = 0;
        if (n <= 1)
            return n;
        if (n == 2)
            return 1;

        unordered_map<int, int> f;
        for (int num : nums)
            maxf = max(maxf, ++f[num]);

        vector<int> buckets(maxf+1, 0);
        for (auto& [k, v] : f)
            buckets[v]++;

        int numbersToRemoveFromArr = (n+1)/2;

        for (int i = maxf; i>0 && numbersToRemoveFromArr > 0; i--)
        {
            if (buckets[i] == 0)
                continue;

            if (numbersToRemoveFromArr - i*buckets[i] >= 0)
            {
                numbersToRemoveFromArr -= i*buckets[i];
                res += buckets[i];
            }
            else
            {
                while (buckets[i] && numbersToRemoveFromArr > 0)
                {
                    numbersToRemoveFromArr -= i;
                    res++;
                    buckets[i]--;
                }
            }
        }
            
        return res;
    }
};
73631