Domain 2MediumMEDIUM

Reduce Array Size To The Half

Use a hash map to count frequencies, sort them descending, and greedily remove elements with highest counts until at least half the array is removed.

Domain: medium•Updated: 2026-09-14
#greedy#hash map#o(n log n)#medium

Problem Breakdown

We are given an integer array arr where we must select a set of distinct integers to remove all their occurrences from the array. The goal is to minimize the size (count) of this chosen set such that at least half (len(arr) // 2) of the original elements are removed.

  • Inputs: An integer list arr.
  • Outputs: A single integer representing the minimum number of unique integers needed in the removal set.
  • Constraints:
    • Array length is even (1≤N≤1051 \le N \le 10^5).
    • Values are positive integers up to 10510^5.

Intuition

To minimize the size of the chosen set, we want each selected integer to remove as many elements from the array as possible. This suggests a greedy strategy: prioritize removing numbers that appear most frequently in arr.

If we pick an element with frequency 4 and another with frequency 1, picking the first one reduces our remaining count by 4 for “cost” of 1 unique number picked. Picking both costs 2 but removes only 5 total elements (less efficient than just picking high frequencies). Therefore, sorting frequencies in descending order allows us to reach the target removal threshold (len(arr) // 2) using the fewest distinct numbers possible.

Approach

  1. Frequency Counting: Iterate through arr and store counts of each unique number using a hash map (e.g., Python’s Counter).
  2. Sort Frequencies: Extract the frequency values from the map into a list and sort them in descending order to prioritize high-frequency elements.
  3. Greedy Accumulation: Iterate through the sorted frequencies, accumulating the total count of removed elements (removed_count) for each unique number processed. Increment our result counter (set_size) with every element added to our removal set.
  4. Termination: Stop as soon as removed_count meets or exceeds half the original array length. Return the current set_size.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N).
    • Counting frequencies takes O(N)O(N) where NN is the number of elements in arr.
    • Sorting the frequency counts takes O(Klog⁡K)O(K \log K), where KK is the number of unique elements (K≤NK \le N). In the worst case (all distinct), this becomes O(Nlog⁡N)O(N \log N). This fits within time limits for N=105N=10^5.
  • Space Complexity: O(K)O(K) or O(N)O(N). We store a hash map for frequencies and an array/list of frequency counts. Since values are bounded by integers, the space is proportional to unique elements found in arr.

Solution

from collections import Counter

def minSetSize(arr):
    # Count frequency of each element in the input array
    freq_map = Counter(arr)
    
    # Extract frequencies and sort descending to prioritize removing high-frequency numbers first.
    sorted_counts = sorted(freq_map.values(), reverse=True)
    
    target_removed = len(arr) // 2
    removed_count = 0
    set_size = 0
    
    for count in sorted_counts:
        # If we have already met the removal requirement, stop immediately
        if removed_count >= target_removed:
            break
        
        # Add current element's frequency to our removal total
        removed_count += count
        
        # Increment the number of unique elements chosen (set size)
        set_size += 1
            
    return set_size

# Example usage for verification:
# print(minSetSize([3,3,3,3,5,5,5,2,2,7])) 

Edge Cases Handled

  • All identical elements: The frequency list contains one large value (equal to NN). One iteration removes everything ≥N/2\ge N/2. Returns 1.
  • Distinct elements: Frequencies are all 1. We need exactly half the array length iterations, returning len(arr) // 2.
  • Large values in input: Since we use a hash map (Counter), the magnitude of integers doesn’t affect complexity or memory usage (only equality matters).