Reduce Array Size to At Least Half — Greedy Frequency Elimination

Problem Statement#

You are given an integer array arr. You can choose a set of integers and remove all occurrences of these integers from the array. Return the minimum size of the set so that at least half of the integers of the array are removed.

Constraints:

• 2 <= arr.length <= 10^5
• arr.length is even.
• 0 <= arr[i] <= 10^5

Examples:

Example 1:
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Removing 3 (4 occurrences) removes 4 elements.
  Remaining = 6 elements, still need to remove more. 
  Remove 5 (3 occurrences): total removed = 7 >= 5 (half of 10). Set size = 2.
 
Example 2:
Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: Remove all 7s (6 occurrences) → empty array. 1 distinct value removed.
 
Example 3:
Input: arr = [1,9]
Output: 1
Explanation: Remove either 1 or 9. 1 element removed ≥ half of 2.

Why This Problem Matters#

Reduce Array Size to At Least Half is a medium problem that tests greedy intuition with frequency-based ordering. Amazon and Meta use it in coding screens because it has a clear optimal substructure: to remove the fewest distinct values while eliminating the most elements, you should always remove the most frequent values first.

This greedy proof is immediate: if you have two strategies — one that picks values in order of decreasing frequency and one that picks in any other order — the frequency-ordered strategy always removes at least as many elements per "distinct value used." This is the same logic behind Huffman coding and many scheduling algorithms.

The problem also tests your fluency with frequency computation and heap-based selection. In Python, the combination of Counter and heapq.nlargest (or building a max-heap) gives a concise, readable solution. In JavaScript, sorting the frequency array descending and greedily summing is equally clean.

A common interview follow-up at Amazon: "What if you could only remove at most k distinct values?" This transforms the problem from a simple greedy to a variant where you select the k highest-frequency values and check if their total removal is enough — a direct application of the top-k selection pattern.

The Core Insight#

The greedy argument is simple: to reach the target of removing at least n/2 elements using the fewest distinct values, always pick the value with the highest remaining frequency. This maximizes the "return on investment" — each distinct value you choose to remove should eliminate as many array elements as possible.

Steps:

1. Count the frequency of each distinct value.
2. Sort frequencies in descending order (or use a max-heap).
3. Greedily accumulate frequencies until the running total reaches n/2.
4. Return the count of distinct values used.

Proof of optimality: Suppose the greedy solution uses k values removing S elements. Any other solution that removes k values must remove fewer elements (since the greedy always picks the k highest frequencies). Therefore the greedy requires the fewest distinct values.

Visual Dry Run#

arr = [3,3,3,3,5,5,5,2,2,7], n=10, target = n/2 = 5
 
Step 1: Count frequencies.
  {3:4, 5:3, 2:2, 7:1}
 
Step 2: Sort by frequency descending.
  [4, 3, 2, 1]
 
Step 3: Greedily pick.
  Pick 4 (remove all 3s): removed=4 < 5. Count=1.
  Pick 3 (remove all 5s): removed=7 >= 5. Count=2. DONE!
 
Answer: 2. ✓
 
arr = [7,7,7,7,7,7], n=6, target=3.
  {7:6}. sorted=[6].
  Pick 6 >= 3. Count=1. ✓

Solution (Optimal)#

from collections import Counter
import heapq
 
def minSetSize(arr):
    count = Counter(arr)
    
    # Max-heap of frequencies (negate for Python's min-heap)
    heap = [-freq for freq in count.values()]
    heapq.heapify(heap)
    
    removed = 0
    target = len(arr) // 2
    result = 0
    
    while removed < target:
        # Remove most frequent value
        removed -= heapq.heappop(heap)  # heap stores negated, so subtract
        result += 1
    
    return result

function minSetSize(arr) {
    // Count frequencies
    const count = new Map();
    for (const n of arr) {
        count.set(n, (count.get(n) || 0) + 1);
    }
    
    // Sort frequencies descending
    const freqs = [...count.values()].sort((a, b) => b - a);
    
    let removed = 0;
    let result = 0;
    const target = arr.length / 2;
    
    for (const freq of freqs) {
        if (removed >= target) break;
        removed += freq;
        result++;
    }
    
    return result;
}

Complexity Analysis:

• Time: O(n + m log m) where n = array length, m = number of distinct values. Counting is O(n), sorting/heapifying is O(m log m), greedy selection is O(k log m) where k is the answer.
• Space: O(m) — frequency map and heap/sorted array of frequencies

Common Mistakes#

• Not reaching exactly half — stopping too early. The condition is removed >= n/2 (at least half). Don't stop at "exactly half" if no single value removal lands on exactly n/2.
• Comparing removed >= target correctly. Since arr.length is always even (given in constraints), target = len(arr) // 2 is exact. But be careful with odd-length arrays if you're generalizing.
• Using a min-heap instead of a max-heap. You want the most frequent values first. In Python, negate frequencies: heap = [-freq for freq in ...].
• Sorting ascending instead of descending. In JavaScript, sort((a,b) => b-a) for descending; sort((a,b) => a-b) would give ascending (wrong for this greedy).
• Treating arr.length as the number of distinct values. n = arr.length (total elements), m = number of distinct values. These are different.

Follow-up Questions#

1. What is the maximum possible answer? In the worst case, how many distinct values might you need to remove?
2. What if you could remove at most k distinct values? What is the maximum number of elements you can remove? (Top-k frequencies sum.)
3. What if the problem asked for at least 1/3 of elements removed? How does the greedy change?
4. Prove formally that the greedy is optimal using an exchange argument.
5. What is the minimum possible answer, and under what input does it occur?
6. Can you solve this in O(n) time using counting sort (since values are bounded)? Yes — bucket sort the frequencies.

Key Takeaways#

• Greedy is optimal: to minimize the number of distinct values removed while eliminating at least n/2 elements, always pick the value with the highest remaining frequency first.
• Count frequencies with Counter, negate them for Python's min-heap to get a max-heap, and greedily accumulate until removed >= n/2.
• In JavaScript, simply sort the frequency array descending and iterate — no explicit heap needed for this problem size.
• The stopping condition is removed >= target (at least half), not exactly half — an accumulation may overshoot and that is correct.
• Time is O(n + m log m) where n = array length and m = number of distinct values; space is O(m).
• Since values are bounded by 10^5, bucket sort on frequencies achieves O(n) — worth mentioning as a follow-up.
• Amazon and Meta use this problem to test whether candidates can prove greedy optimality; always articulate the exchange argument: swapping any high-frequency choice with a lower-frequency one can only worsen the result.