Code Implementation

from collections import Counter

class Solution:
    def minSetSize(self, arr):
        freq = Counter(arr)
        counts = sorted(freq.values(), reverse=True)
        removed = 0
        res = 0
        half = len(arr) // 2
        for c in counts:
            removed += c
            res += 1
            if removed >= half:
                return res
      

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

class Solution {
public:
    int minSetSize(std::vector<int>& arr) {
        std::unordered_map<int, int> freq;
        for (int n : arr) freq[n]++;
        std::vector<int> counts;
        for (auto &p : freq) counts.push_back(p.second);
        std::sort(counts.rbegin(), counts.rend());
        int removed = 0, res = 0, half = arr.size() / 2;
        for (int c : counts) {
            removed += c;
            res++;
            if (removed >= half) return res;
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int minSetSize(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int n : arr) freq.put(n, freq.getOrDefault(n, 0) + 1);
        List<Integer> counts = new ArrayList<>(freq.values());
        counts.sort(Collections.reverseOrder());
        int removed = 0, res = 0, half = arr.length / 2;
        for (int c : counts) {
            removed += c;
            res++;
            if (removed >= half) return res;
        }
        return res;
    }
}
      

var minSetSize = function(arr) {
    let freq = {};
    for (let n of arr) freq[n] = (freq[n] || 0) + 1;
    let counts = Object.values(freq).sort((a, b) => b - a);
    let removed = 0, res = 0, half = arr.length / 2;
    for (let c of counts) {
        removed += c;
        res++;
        if (removed >= half) return res;
    }
};
      

Problem Description

You are given an integer array arr. Your task is to remove as few elements as possible from arr so that at least half of the elements are removed. However, you can only remove all occurrences of a chosen integer at a time (i.e., you remove entire "sets" of the same value).
Return the minimum number of unique integers you need to choose so that removing all their occurrences reduces the size of arr by at least half.
Key constraints:

• Each time you pick a number, you must remove all its occurrences.
• There is always at least one valid solution.
• You cannot partially remove occurrences; you must remove all of a chosen value at once.

Thought Process

At first, it might seem like you have to try all possible combinations of numbers to remove, but this would be very slow for large arrays.
The key insight is that removing numbers that appear most frequently will reduce the array size the fastest. So, instead of brute-forcing all possibilities, we should focus on the numbers with the highest counts.
This leads to a greedy approach: always remove the number with the highest frequency next, and keep track of how many elements have been removed so far.
This is much more efficient than trying every possible subset of numbers.

Solution Approach

The solution can be broken down into the following steps:

1. Count the frequency of each number in arr. We use a hash map (dictionary) for this, since looking up and updating counts is fast (O(1) time per operation).
2. Sort the frequencies from largest to smallest. This way, we can remove the most impactful numbers first.
3. Iterate through the sorted list, removing all occurrences of each number, and keep a running total of how many elements we've removed.
4. Stop once we've removed at least half of the original array. At this point, the number of unique numbers we've picked is our answer.

This approach is efficient because it only requires counting, sorting, and a single pass through the sorted frequencies.

Example Walkthrough

Let's say arr = [3,3,3,3,5,5,5,2,2,7].

• Step 1: Count frequencies: 3 appears 4 times, 5 appears 3 times, 2 appears 2 times, 7 appears 1 time.
• Step 2: Sort frequencies: [4, 3, 2, 1]
• Step 3: Remove the highest frequency number (4 of 3): removed = 4, sets used = 1.
• Step 4: Check if removed >= half (10 / 2 = 5)? Not yet (removed = 4).
• Step 5: Remove next highest (3 of 5): removed = 7, sets used = 2.
• Step 6: Now removed = 7 >= 5, so we stop. Answer = 2.

This means we only need to remove two unique numbers (3 and 5) to reduce the array size by at least half.

Time and Space Complexity

Brute-force approach:

• Would require checking all subsets of unique numbers: exponential time (O(2^n)), where n is the number of unique numbers. This is impractical for large inputs.

• Counting frequencies: O(n), where n is the length of arr.
• Sorting frequencies: O(k log k), where k is the number of unique numbers (at most n).
• Iterating through counts: O(k).
• Total time complexity: O(n + k log k)
• Space complexity: O(k) for the frequency map and counts array.

This is efficient and suitable for large arrays.

Summary

To solve "Reduce Array Size to The Half", we count how many times each number appears, then repeatedly remove all occurrences of the most frequent numbers until we've removed at least half the array.
The greedy approach works because removing the most frequent numbers is always optimal for minimizing the number of sets chosen. This method is both simple and efficient, making it a great example of using counting and sorting to solve a problem optimally.