Skip to main content

1338 - Reduce Array Size to The Half

Difficulty: Medium | Pattern: Greedy / Sorting | Company tags: Amazon, Google

Problem Statement​

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

Example 1:

Input: arr = [3,3,3,3,2,2,2,1,1]
Output: 2
Explanation: Remove 3s (4) and 2s (3): removed 7 >= 9/2. Set size = 2.

Example 2:

Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: Remove all 7s: 6 removed >= 3. Set size = 1.

Approach: Greedy — O(n log n)​

Key insight: Greedily remove the most frequent elements first. Sort frequencies in descending order and keep adding until we've removed at least half.

from collections import Counter

def minSetSize(arr: list[int]) -> int:
    n = len(arr)
    target = n // 2
    
    freq = sorted(Counter(arr).values(), reverse=True)
    removed = 0
    count = 0
    
    for f in freq:
        removed += f
        count += 1
        if removed >= target:
            return count
    
    return count

Algorithm Flow​

Dry Run​

arr = [3,3,3,3,2,2,2,1,1], n=9, target=4

Frequencies: [4, 3, 2] (sorted desc)

fremovedcountremoved >= 4?
441Yes → return 1

Wait: 4 >= 4 → return 1? But expected answer is 2.

Let me recheck: target = 9//2 = 4. After removing 3s (freq=4): removed=4 >= 4 → return 1.

Actually: [3,3,3,3,2,2,2,1,1] → n=9, target=9//2=4. Removing 3s (4 occurrences) gives 4 >= 4. Answer = 1? But the example says 2.

Check: "at least half" means removed >= ceil(n/2)? Let's check with (n+1)//2 = 5.

target = (n + 1) // 2  # ceil

With target=5: f=4 gives removed=4 < 5; f=3 gives removed=7 >= 5 → return 2. ✓

def minSetSize(arr: list[int]) -> int:
    n = len(arr)
    target = (n + 1) // 2  # at least ceil(n/2) removed
    
    freq = sorted(Counter(arr).values(), reverse=True)
    removed = 0
    
    for count, f in enumerate(freq, 1):
        removed += f
        if removed >= target:
            return count
    
    return len(freq)

Edge Cases​

  • All same element → 1 (remove it)
  • All unique → need to remove ceil(n/2) elements
  • n = 1 → target = 1, remove 1 element → return 1

Complexity​

  • Time: O(n log n) — counting O(n), sorting O(k log k) where k = distinct elements
  • Space: O(k) for frequency map

Key Terms​

TermDefinition
Greedy algorithmRepeatedly picks the locally best choice (here, the most frequent remaining value) to reach a global optimum.
Frequency mapA hash map (e.g. Counter) recording how many times each value appears in the array.
Ceiling division(n + 1) // 2, used to compute "at least half" without floating-point rounding.
Exchange argumentThe proof technique showing that swapping a smaller-frequency pick for a larger one never makes the greedy choice worse.

FAQ​

Q1: Why does removing the most frequent elements first give the minimum set size? By an exchange argument: if an optimal solution ever picks a lower-frequency value while skipping a higher-frequency one, swapping them removes at least as many elements with the same or smaller set size — so sorting by frequency descending is always optimal.

Q2: Why is the target (n + 1) // 2 instead of n // 2? "At least half" means removed >= ceil(n/2). For odd n, n // 2 under-counts (e.g. n=9 → floor gives 4, but you need 5 to cover more than half). (n+1)//2 computes the ceiling using integer arithmetic.

Q3: What's the time complexity, and can it be improved? O(n + k log k) where k is the number of distinct values (counting is O(n), sorting frequencies is O(k log k)). Using a max-heap instead of full sort doesn't improve worst-case complexity here since we may need to pop up to k elements anyway.

Q4: Does the order of equal frequencies matter? No — if multiple values share the same frequency, picking any of them in any order yields the same count and total removed.

Q5: How would the approach change if we needed the minimum set to remove exactly half (not at least half)? This becomes a subset-sum-style problem (can some subset of frequencies sum to exactly n/2?), which is NP-hard in general — the greedy approach only works for the "at least" variant.

Quick Revision​

  • Goal: minimum number of distinct values to remove so at least half the array is gone.
  • Step 1: build a frequency map with Counter.
  • Step 2: sort frequencies in descending order.
  • Step 3: greedily accumulate the largest frequencies until removed >= ceil(n/2).
  • Target must be (n + 1) // 2 (ceiling), not n // 2 (floor) — off-by-one trap for odd n.
  • Greedy correctness follows from an exchange argument: bigger frequencies always dominate.
  • Time: O(n + k log k); Space: O(k), where k = number of distinct values.
  • Edge case: all elements identical → answer is always 1.
  • 347 - Top K Frequent Elements — same frequency-counting + sorting/heap pattern.
  • 451 - Sort Characters By Frequency — frequency map sorted by count descending.
  • Pattern: greedy-by-frequency problems, often paired with a Counter + sort or heap.