Reduce Array Size to The Half — Editorial

Opening the reading…

Intuitionwhy frequency, not value, determines the choice

Deleting one distinct number removes all of its occurrences, so every possible choice has a simple value: its frequency. The actual integer does not matter. If one number appears 20 times and another appears twice, choosing the first removes far more array elements while increasing the set size by exactly one.

The target is half of the original array, and every chosen number costs one slot in the set. To reach that target with as few slots as possible, take the largest available frequencies first. After sorting all frequencies from largest to smallest, the first prefix whose sum reaches half gives the minimum answer: replacing one of those choices with a smaller frequency could only reduce the number removed.

Approach

Count how many times each distinct integer appears, because deleting a value removes its entire frequency rather than one occurrence.

Copy the frequencies into a separate vector, because the values themselves are irrelevant once their counts are known.

Sort the frequency vector in descending order, so each next choice removes at least as many elements as any unchosen value.

Set the target to arr.size() / 2 and keep a running total of removed elements, because the array length is even and reaching this target is exactly the required condition.

Take frequencies from the front one at a time, increasing the answer for each chosen distinct value; skipping a larger frequency for a smaller one cannot help minimize the number of choices.

Stop as soon as removed is at least target, because the problem asks for at least half and any further choice would only make the set larger.

Return the number of frequencies taken, which is the size of the chosen set rather than the number of individual elements removed.

Complexitycounting distinct values, then sorting their frequencies

MEASURE	BOUND	WHY
Time	O(n + m log m)	The hash-map pass processes each of the n elements once. Building the frequency vector touches each of the m distinct keys, and sorting those m counts costs O(m log m); the final scan visits each count at most once.
Space	O(m) extra	The frequency map and the vector of counts hold one entry per distinct value. The returned set is not materialized, so there is no output storage to count; in the worst case m equals n, making the extra space O(n).

Here n is the length of arr and m is the number of distinct values in arr.

Annotated solutionC++ · frequency map plus descending sort

CPPCount each value, sort frequencies from largest to smallest, and stop at half the original length.

#include <algorithm>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int x : arr) {
            freq[x]++;
        }

        vector<int> counts;
        for (const auto& entry : freq) {
            counts.push_back(entry.second);
        }

        sort(counts.rbegin(), counts.rend());

        int removed = 0;
        int half = static_cast<int>(arr.size()) / 2;
        int answer = 0;

        for (int count : counts) {
            removed += count;
            answer++;
            if (removed >= half) {
                break;
            }
        }

        return answer;
    }
};

The important placement is the stopping check after adding a frequency. That frequency belongs to the chosen set, even if it carries removed past the target, so answer must increase before the check. Using >= rather than > also handles the exact-half case without selecting an unnecessary extra value.

Counting frequencies without sortingan optimization that uses the bounded value range

Because every value is between 1 and 100000, you can replace the hash map with a direct frequency array. After counting values, group those frequencies by their size: bucket f tells you how many distinct values occur exactly f times. Reading the buckets from n down to 1 is counting sort over the frequencies, so this avoids the m log m comparison sort.

CPPDirect-address counting followed by frequency buckets; no comparison sort is needed.

#include <vector>

using namespace std;

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        const int maxValue = 100000;
        vector<int> valueFrequency(maxValue + 1, 0);

        for (int x : arr) {
            valueFrequency[x]++;
        }

        vector<int> frequencyBucket(arr.size() + 1, 0);
        for (int x = 1; x <= maxValue; x++) {
            if (valueFrequency[x] > 0) {
                frequencyBucket[valueFrequency[x]]++;
            }
        }

        int half = static_cast<int>(arr.size()) / 2;
        int removed = 0;
        int answer = 0;

        for (int frequency = static_cast<int>(arr.size()); frequency >= 1; frequency--) {
            while (frequencyBucket[frequency] > 0 && removed < half) {
                removed += frequency;
                answer++;
                frequencyBucket[frequency]--;
            }
            if (removed >= half) {
                break;
            }
        }

        return answer;
    }
};

This version is an optimization only when the value range is known and small enough to allocate. Its time is O(n + V), where V is the maximum possible value, and its extra space is O(n + V). The original map-and-sort version is more general because it does not depend on that range; it is usually the clearer choice when values can be arbitrary.