Problem Statement: Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example:

Input: arr = [5,5,4], k = 1 Output: 1 Explanation: Remove the single 4, only 5 is left.

Input: arr = [4,3,1,1,3,3,2], k = 3 Output: 2 Explanation: Remove the 4, 2 and either one of the two 1s or three 3s. 1 and 2 left.

Solution: The solution can be obtained using two steps:

1. Count the frequency of all elements in an array and create a dictionary.
2. Sort the dictionary values in non-descending order and remove the first k values.

The rationale behind this solution is that we want to remove the least frequent elements from the array, so that we can preserve as many remaining elements as possible. We create a dictionary to map each unique element to its frequency. We then need to sort the dictionary by its values. We want to maintain the least frequent elements in the array, hence we proceed to remove the k least frequent elements in the array.

Code:

def findLeastNumOfUniqueInts(arr, k): # Step 1: Create a dictionary that maps each unique element to its frequency frequency_dict = {} for element in arr: if element not in frequency_dict: frequency_dict[element] = 1 else: frequency_dict[element] += 1

# Step 2: Sort the dictionary by its values and remove the first k elements
sorted_dict = sorted(frequency_dict.items(), key=lambda x:x[1])
count = 0
for i in range(len(sorted_dict)):
    count += sorted_dict[i][1]
    if count > k:
        return len(sorted_dict) - i
return 0

Test the function

arr1 = [5,5,4] k1 = 1 print(findLeastNumOfUniqueInts(arr1, k1)) # Output: 1

arr2 = [4,3,1,1,3,3,2] k2 = 3 print(findLeastNumOfUniqueInts(arr2, k2)) # Output: 2

The time complexity of the code is O(nlogn), considering the sorting operation.

1