Solution Explanation: Least Number of Unique Integers After K Removals

This problem asks to find the minimum number of unique integers remaining in an array after removing exactly k elements. The optimal approach involves using a hash table (or dictionary) to count the frequency of each integer and then employing a greedy strategy.

Algorithm:

1. Frequency Counting: Use a hash table (e.g., Counter in Python, HashMap in Java) to count the occurrences of each integer in the input array arr.

2. Frequency Sorting: Create a list or array containing the frequencies of each unique integer. Sort this list in ascending order. This is crucial because the greedy strategy prioritizes removing the least frequent elements first.

3. Greedy Removal: Iterate through the sorted frequency list. For each frequency freq, subtract freq from k.

   • If k becomes less than or equal to 0, it means we've removed enough elements. The remaining number of unique integers is the length of the frequency list minus the index of the current frequency.

   • If we iterate through the entire frequency list and k is still greater than 0, it means we can remove all the elements, resulting in 0 unique integers remaining.

Code Implementation (Python):

from collections import Counter
 
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)  # Count frequencies
        freqs = sorted(cnt.values())  # Sort frequencies in ascending order
        
        for i, freq in enumerate(freqs):
            k -= freq
            if k <= 0:
                return len(freqs) - i  # Return remaining unique integers
        return 0  # All elements removed

Code Implementation (Java):

import java.util.*;
 
class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : arr) {
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }
 
        List<Integer> freqs = new ArrayList<>(cnt.values());
        Collections.sort(freqs);
 
        for (int i = 0; i < freqs.size(); i++) {
            k -= freqs.get(i);
            if (k <= 0) {
                return freqs.size() - i;
            }
        }
        return 0;
    }
}

Time Complexity Analysis:

• Frequency Counting: O(n), where n is the length of the input array.
• Sorting: O(m log m), where m is the number of unique integers (m ≤ n).
• Greedy Removal: O(m)

Therefore, the overall time complexity is dominated by the sorting step: O(n log n) in the worst case (when all elements are unique).

Space Complexity Analysis:

• The hash table to store frequencies: O(m)
• The sorted frequency list: O(m)

The space complexity is O(n) in the worst case (when all elements are unique).

Example Walkthrough:

Let's consider arr = [4,3,1,1,3,3,2], k = 3.

1. cnt will be {4:1, 3:3, 1:2, 2:1}.
2. freqs will be [1, 1, 2, 3] after sorting.
3. Iteration:
   • k starts at 3.
   • k -= 1 (first 1), k = 2.
   • k -= 1 (second 1), k = 1.
   • k -= 2 (2), k = -1. We stop here because k is negative.
   • The number of unique integers remaining is len(freqs) - i = 4 - 3 = 1. This is incorrect, should be 2. The code has a small bug because it does not handle the case when k becomes less than 0. it should be len(freqs) -i +1.

The corrected Python code should be:

from collections import Counter
 
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)  # Count frequencies
        freqs = sorted(cnt.values())  # Sort frequencies in ascending order
        
        for i, freq in enumerate(freqs):
            k -= freq
            if k < 0:
                return len(freqs) - i  # Return remaining unique integers
        return 0  # All elements removed