Problem Description

You have an integer array arr. Your task is to select a set of distinct integers from this array and remove all occurrences of each selected integer from the array.

The goal is to find the minimum number of distinct integers you need to select such that after removing all their occurrences, at least half of the original array elements are removed.

For example, if you have an array [3,3,3,3,5,5,5,2,2,7] with 10 elements:

• If you choose to remove all occurrences of 3 (4 elements) and all occurrences of 5 (3 elements), you remove 7 elements total
• Since 7 ≥ 10/2, you've removed at least half the array
• You selected 2 distinct integers (3 and 5), so the answer would be 2

The solution approach counts the frequency of each number in the array using a Counter. It then sorts these frequencies in descending order (using most_common()). By greedily selecting the most frequent numbers first and keeping track of how many elements have been removed (m), the algorithm continues adding numbers to the set until at least half of the array elements are removed (m * 2 >= len(arr)). This greedy approach ensures the minimum set size because removing the most frequent numbers first maximizes the number of elements removed per selection.

Intuition

To minimize the number of distinct integers we need to select, we want to maximize the impact of each selection. Since removing a number removes all its occurrences, we should prioritize removing the numbers that appear most frequently in the array.

Think of it this way: if we need to remove at least half of the array elements, and we can only remove complete sets of identical numbers, then we want each selection to contribute as much as possible toward our goal.

For instance, if we have a number that appears 100 times and another that appears just once, removing the frequent number gets us much closer to the "half removed" target with just one selection, whereas we'd need to remove many infrequent numbers to achieve the same effect.

This naturally leads to a greedy strategy: sort the numbers by their frequency in descending order and keep selecting the most frequent ones until we've removed at least half of the array. This is optimal because:

1. Each selection removes all occurrences of that number
2. Selecting high-frequency numbers first means fewer selections needed overall
3. We stop as soon as we reach the threshold of removing half the elements

The key insight is that the actual values of the numbers don't matter - only their frequencies do. That's why we can use a Counter to get frequencies, sort them in descending order, and greedily pick from the top until we've removed enough elements.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The implementation follows a counting and sorting strategy to solve this problem efficiently.

Step 1: Count Frequencies

cnt = Counter(arr)

We use Python's Counter from the collections module to create a frequency map. This gives us a dictionary where keys are the unique numbers in arr and values are their occurrence counts.

Step 2: Sort by Frequency

for _, v in cnt.most_common():

The most_common() method returns a list of (element, count) pairs sorted by count in descending order. We iterate through this list, but we only need the count value v (not the actual number), so we use _ to ignore the element.

Step 3: Greedy Selection

ans = m = 0
for _, v in cnt.most_common():
    m += v
    ans += 1
    if m * 2 >= len(arr):
        break

We maintain two variables:

• m: tracks the total number of elements removed so far
• ans: counts how many distinct numbers we've selected

For each iteration:

1. Add the current frequency v to m (removing all occurrences of this number)
2. Increment ans by 1 (we've selected one more distinct number)
3. Check if m * 2 >= len(arr), which is equivalent to checking if m >= len(arr) / 2
4. If we've removed at least half the elements, we break and return ans

Time Complexity: O(n log n) where n is the length of the array, dominated by the sorting operation in most_common().

Space Complexity: O(n) for storing the frequency counter.

The algorithm is optimal because it always selects the minimum number of distinct integers needed by greedily choosing the most frequent ones first.

Example Walkthrough

Let's walk through the solution with the array [2,2,1,3,3,3,4]:

Step 1: Count Frequencies Using Counter(arr), we get:

• 1 appears 1 time
• 2 appears 2 times
• 3 appears 3 times
• 4 appears 1 time

Step 2: Sort by Frequency (Descending) After calling most_common(), we get the order:

1. 3 with frequency 3
2. 2 with frequency 2
3. 1 with frequency 1 (could be either order with 4)
4. 4 with frequency 1

Step 3: Greedy Selection We need to remove at least ⌈7/2⌉ = 4 elements.

Let's trace through the iterations:

• Iteration 1: Select number 3

  • Add frequency 3 to m: m = 0 + 3 = 3
  • Increment ans: ans = 1
  • Check: Is 3 * 2 >= 7? No (6 < 7), continue

• Iteration 2: Select number 2

  • Add frequency 2 to m: m = 3 + 2 = 5
  • Increment ans: ans = 2
  • Check: Is 5 * 2 >= 7? Yes (10 >= 7), break!

Result: We need to select 2 distinct integers (numbers 3 and 2). By removing all occurrences of these two numbers, we remove 5 elements from the 7-element array, which is more than half.

The greedy approach works because selecting 3 first (the most frequent) removes 3 elements with just one selection, whereas if we had started with less frequent numbers like 1 or 4, we would need more selections to reach our target.

Solution Implementation

Time and Space Complexity

The time complexity is O(n log n), where n is the length of the array arr. This complexity arises from:

• Creating the Counter takes O(n) time to iterate through all elements
• The most_common() method internally sorts the counter items by frequency, which takes O(k log k) time where k is the number of unique elements. In the worst case, k = n (all elements are unique), giving us O(n log n)
• The iteration through the sorted items takes at most O(k) = O(n) time

The dominant operation is the sorting step, resulting in overall time complexity of O(n log n).

The space complexity is O(n). This comes from:

• The Counter object stores at most n unique elements (in the worst case when all elements are different), requiring O(n) space
• The most_common() method creates a sorted list of the counter items, which also requires O(k) = O(n) space in the worst case
• Other variables (ans, m, loop variables) use O(1) space

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Division vs Float Division Confusion

A common mistake is using integer division when checking if half the elements are removed:

# WRONG - This can cause incorrect results due to integer division
if removed_count >= len(arr) // 2:  
    break

Why it's wrong: For an array of length 5, len(arr) // 2 equals 2, but we actually need to remove at least 3 elements (which is ⌈5/2⌉ = 3). This would incorrectly return after removing only 2 elements.

Correct approach: Use multiplication to avoid division issues:

if removed_count * 2 >= len(arr):
    break

2. Modifying the Array During Iteration

Some might try to actually remove elements from the original array:

# WRONG - Don't modify the array
for num in selected_numbers:
    arr = [x for x in arr if x != num]  # This is unnecessary and inefficient

Why it's wrong: The problem only asks for the count of distinct integers to select, not to actually modify the array. This approach is inefficient (O(n²)) and unnecessary.

Correct approach: Work with frequencies only, never modify the original array.

3. Not Handling Edge Cases

Failing to consider edge cases like:

• Empty array (though typically constraints ensure non-empty)
• Array with all identical elements
• Array with all unique elements

Solution: The current approach naturally handles these cases:

# For array [1,1,1,1], only 1 distinct integer needed
# For array [1,2,3,4], need 2 distinct integers to remove half

4. Sorting in Wrong Order

Sorting frequencies in ascending order instead of descending:

# WRONG - This gives suboptimal result
for _, v in sorted(frequency_counter.values()):  # Ascending order
    # This would select less frequent elements first

Why it's wrong: Selecting less frequent elements first requires more distinct integers to reach half the array size.

Correct approach: Always use most_common() or sort in descending order to ensure the greedy approach works optimally.