Problem Description

You are given an array of integers arr and an integer k. Your task is to remove exactly k elements from the array such that the number of unique integers remaining in the array is minimized. Return the least number of unique integers after removing exactly k elements.

For example, if arr = [5, 5, 4] and k = 1, you can remove one element. If you remove one 5, you'll have [5, 4] with 2 unique integers. If you remove the 4, you'll have [5, 5] with only 1 unique integer. So the answer would be 1.

The strategy is to remove integers that appear less frequently first, as this will reduce the number of unique integers more efficiently. By removing all occurrences of integers with smaller frequencies first, you can minimize the total number of unique integers remaining.

Intuition

To minimize the number of unique integers after removing k elements, we need to think about which elements to remove first. The key insight is that we should prioritize removing integers that appear less frequently in the array.

Why? Consider this: if an integer appears only once, removing that single element eliminates one unique integer entirely. If an integer appears 5 times, we'd need to remove all 5 occurrences to eliminate that unique integer. So with limited removals (k), it's more efficient to target integers with lower frequencies.

The greedy approach works here: sort the integers by their frequency counts in ascending order, then remove them starting from the least frequent ones. For each unique integer, we remove all its occurrences. We keep removing until we've used up our k removals.

For example, if we have frequencies [1, 1, 2, 3, 4] and k = 4, we can remove the integers with frequencies 1 and 1 (using 2 removals), then the integer with frequency 2 (using 2 more removals, totaling 4). This eliminates 3 unique integers, leaving us with 2 unique integers remaining.

By counting frequencies first, sorting them, and then greedily removing from smallest to largest frequency, we ensure we're eliminating the maximum number of unique integers possible with our k removals.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows these steps:

1. Count frequencies: Use a hash table (Counter in Python) to count how many times each integer appears in the array. This gives us a mapping from each unique integer to its frequency.

2. Sort frequencies: Extract just the frequency values from the hash table and sort them in ascending order. We don't need to track which integer has which frequency - we only care about the frequency values themselves.

3. Greedy removal: Iterate through the sorted frequencies from smallest to largest. For each frequency value v:

   • Subtract v from k (representing the removal of all occurrences of that integer)
   • If k becomes negative, it means we couldn't fully remove this integer with our remaining removals. The number of unique integers left is the total number of unique integers minus the number we've successfully removed (which is the current index i)
   • If k is still non-negative, continue to the next frequency

4. Return result: If we successfully process all frequencies without k going negative, it means we've removed all unique integers, so return 0.

The algorithm works because:

• By processing frequencies in ascending order, we maximize the number of unique integers we can completely remove
• We keep track of our progress using the index i in the sorted frequency list
• When k goes negative, we know exactly how many unique integers we've eliminated (i) and can calculate how many remain (len(cnt) - i)

Time complexity: O(n log n) for sorting the frequencies, where n is the number of unique integers. Space complexity: O(n) for the hash table storing the frequencies.

Example Walkthrough

Let's walk through the solution with arr = [4, 3, 1, 1, 3, 3, 2] and k = 3.

Step 1: Count frequencies

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

So our frequency map is: {1: 2, 2: 1, 3: 3, 4: 1}

Step 2: Sort frequencies Extract the frequency values: [2, 1, 3, 1] Sort them in ascending order: [1, 1, 2, 3]

Step 3: Greedy removal We have k = 3 removals available. Process frequencies from smallest to largest:

• Index 0: frequency = 1

  • Remove this integer completely (uses 1 removal)
  • k = 3 - 1 = 2 (still positive, continue)

• Index 1: frequency = 1

  • Remove this integer completely (uses 1 removal)
  • k = 2 - 1 = 1 (still positive, continue)

• Index 2: frequency = 2

  • Try to remove this integer completely (would use 2 removals)
  • k = 1 - 2 = -1 (negative! Can't fully remove this integer)
  • Stop here

Step 4: Calculate result

• Total unique integers originally: 4
• Successfully removed integers: 2 (at indices 0 and 1)
• Remaining unique integers: 4 - 2 = 2

The answer is 2. We removed the two integers that appeared once (integers 2 and 4), leaving us with integers 1 and 3 in the array.

Solution Implementation

Time and Space Complexity

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

• Creating the Counter takes O(n) time to count all elements
• Getting the values from Counter takes O(m) time where m is the number of unique elements (at most n)
• Sorting the frequency values takes O(m log m) time, which is at most O(n log n)
• The enumeration loop iterates through at most m values, taking O(m) time
• Overall: O(n) + O(m log m) + O(m) = O(n log n) since m ≤ n

The space complexity is O(n), where n is the length of the array arr. This is because:

• The Counter dictionary stores at most n key-value pairs (when all elements are unique)
• The sorted list of values creates a new list of size at most n
• Overall: O(n) + O(n) = O(n)

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

Common Pitfalls

Pitfall 1: Attempting to Track Which Elements to Remove

A common mistake is trying to maintain which specific elements are being removed from the array, rather than just working with frequencies. This leads to unnecessary complexity.

Incorrect approach:

def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
    frequency_map = Counter(arr)
    # Trying to sort by value AND track the keys
    sorted_items = sorted(frequency_map.items(), key=lambda x: x[1])
  
    removed_elements = set()
    for value, freq in sorted_items:
        if k >= freq:
            k -= freq
            removed_elements.add(value)  # Unnecessary tracking
        else:
            break
  
    return len(frequency_map) - len(removed_elements)

Why it's problematic: We don't need to know which specific integers we're removing - we only need to count how many unique integers remain.

Pitfall 2: Off-by-One Error in Counting Remaining Elements

Another frequent error occurs when k becomes negative, leading to incorrect calculation of remaining unique integers.

Incorrect approach:

def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
    frequency_map = Counter(arr)
    sorted_frequencies = sorted(frequency_map.values())
  
    for index, frequency in enumerate(sorted_frequencies):
        k -= frequency
        if k < 0:
            # Wrong! This counts the current element as removed
            return len(frequency_map) - index - 1
  
    return 0

Why it's problematic: When k goes negative, it means we couldn't fully remove the element at the current index. The number of completely removed elements is exactly index, not index + 1.

Pitfall 3: Not Handling Edge Cases Properly

Failing to consider when k equals 0 or when k is greater than or equal to the array length.

Incorrect approach:

def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
    if k == 0:  # Unnecessary special case
        return len(set(arr))
  
    frequency_map = Counter(arr)
    sorted_frequencies = sorted(frequency_map.values())
  
    # Missing check for k >= len(arr)
    for index, frequency in enumerate(sorted_frequencies):
        k -= frequency
        if k < 0:
            return len(frequency_map) - index
  
    # May not reach here if logic is wrong

Solution: The original code handles these cases naturally without special checks. When k = 0, the first frequency subtraction will make k negative, returning the full count. When k >= len(arr), all frequencies will be processed and the function returns 0.