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 ().
- Values are positive integers up to .
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
- Frequency Counting: Iterate through
arrand store counts of each unique number using a hash map (e.g., Python’sCounter). - Sort Frequencies: Extract the frequency values from the map into a list and sort them in descending order to prioritize high-frequency elements.
- 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. - Termination: Stop as soon as
removed_countmeets or exceeds half the original array length. Return the currentset_size.
Complexity Analysis
- Time Complexity: .
- Counting frequencies takes where is the number of elements in
arr. - Sorting the frequency counts takes , where is the number of unique elements (). In the worst case (all distinct), this becomes . This fits within time limits for .
- Counting frequencies takes where is the number of elements in
- Space Complexity: or . 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 ). One iteration removes everything . 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).