Reduce Array Size to The Half

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

1. 1Count how many times each distinct integer appears, because deleting a value removes its entire frequency rather than one occurrence.
2. 2Copy the frequencies into a separate vector, because the values themselves are irrelevant once their counts are known.
3. 3Sort the frequency vector in descending order, so each next choice removes at least as many elements as any unchosen value.
4. 4Set 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.
5. 5Take 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.
6. 6Stop 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.
7. 7Return 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

Annotated solutionC++ · frequency map plus descending sort

#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.

#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.

Common mistakestwo wrong code shapes that change the minimum