Reduce Array Size to The Half

medium heap greedy frequency

Problem

You are given an integer array arr. You may choose a set of integers and remove every occurrence of those integers from the array. Return the minimum size of that set so that at least half of the integers of the array are removed.

Inputarr = [3,3,3,3,5,5,5,2,2,7]

Output2

Removing {3,5} deletes 4 + 3 = 7 elements, leaving size 3 ≤ 5. Two distinct values suffice to remove at least half.

Inputarr = [7,7,7,7,7,7]

Output1

Only one distinct value exists; removing 7 empties the array.

arr (comma-separated)

def min_set_size(arr):
    counts = Counter(arr)
    heap = [-c for c in counts.values()]
    heapq.heapify(heap)
    half = len(arr) // 2
    removed = 0
    picked = 0
    while removed < half:
        removed += -heapq.heappop(heap)
        picked += 1
    return picked

function minSetSize(arr) {
  const counts = new Map();
  for (const x of arr) counts.set(x, (counts.get(x) || 0) + 1);
  const heap = [...counts.values()].sort((a, b) => b - a);
  const half = arr.length / 2;
  let removed = 0, picked = 0;
  while (removed < half) {
    removed += heap[picked];
    picked += 1;
  }
  return picked;
}

int minSetSize(int[] arr) {
    Map<Integer, Integer> counts = new HashMap<>();
    for (int x : arr) counts.merge(x, 1, Integer::sum);
    PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> b - a);
    heap.addAll(counts.values());
    int half = arr.length / 2, removed = 0, picked = 0;
    while (removed < half) {
        removed += heap.poll();
        picked++;
    }
    return picked;
}

int minSetSize(vector<int>& arr) {
    unordered_map<int, int> counts;
    for (int x : arr) counts[x]++;
    priority_queue<int> heap;
    for (auto& p : counts) heap.push(p.second);
    int half = arr.size() / 2, removed = 0, picked = 0;
    while (removed < half) {
        removed += heap.top();
        heap.pop();
        picked++;
    }
    return picked;
}

Explanation

Removing a value deletes all of its occurrences at once, so the cost of choosing a value is one set-slot but the payoff is its frequency. To remove at least half the array with the fewest distinct values, we should always spend our next pick on the value that still has the highest frequency.

First we build a frequency table with a hash map: count how many times each distinct value appears. Only the frequencies matter from here on — the actual values are irrelevant to the answer.

We push every frequency into a max-heap (a priority queue ordered largest-first). The heap lets us repeatedly extract the current biggest frequency in O(log k) time, where k is the number of distinct values.

We keep a running total removed and a counter picked. While removed is still below half = n / 2, we pop the largest frequency, add it to removed, and increment picked. The moment removed reaches half, picked is the minimum set size.

This greedy choice is optimal because frequencies are independent: taking the largest available frequency first never hurts, and it maximizes progress toward the half threshold per pick. For example [3,3,3,3,5,5,5,2,2,7] has frequencies {4,3,2,1} and half is 5; popping 4 then 3 reaches 7 ≥ 5 after two picks, so the answer is 2.

Time: O(n + k log k) Space: O(k)