Least Number of Unique Integers after K Removals

class Solution {
public:
    int leastUniqueAfterRemovals(vector<int>& nums, int k) {
        unordered_map<int, int> freqMap;
        for (int num : nums) {
            freqMap[num]++;
        }

        int size = nums.size();
        vector<int> freqCount(size + 1, 0);

        for (auto pair : freqMap) {
            freqCount[pair.second]++;
        }

        int remaining = freqMap.size();

        for (int freq = 1; freq <= size; freq++) {
            int maxRemove = min(k / freq, freqCount[freq]);
            k -= freq * maxRemove;
            remaining -= maxRemove;

            if (k < freq) {
                return remaining;
            }
        }

        return 0;
    }
};

The provided C++ solution solves the problem of finding the least number of unique integers in an array after removing k elements. The process involves the following steps:

1. Initialize an unordered map (freqMap) to track the frequency of each integer in the array.
2. Traverse the input array, placing each integer and its frequency into the freqMap.
3. Set up a vector freqCount to maintain counts of integers having the same occurrence. The size considers the maximum potential frequency as the number of elements in nums.
4. Populate the freqCount vector using the data in freqMap.
5. Variable remaining, representing the count of unique integers left after removal, is initialized to the size of freqMap.
6. Loop through possible frequencies. For each frequency, determine the maximum number of integers you can wholly remove without exceeding k. Adjust k and remaining accordingly.
7. If k becomes less than the current frequency, meaning you cannot fully remove another group of integers of this frequency, return the number of remaining unique integers.
8. If k allows for removal of all candidate integers of the highest frequency without reaching zero, continue until exhausted or until all removals have been performed.

The loop ensures that each element's removal contribution to achieving the smallest number of unique integers is considered optimally. This method positions the solution to effectively reduce the array’s unique integer count, considering both the frequency of elements and the allowable number of removals, k.

class Solution {
    public int minUniqueIntegers(int[] elements, int removals) {
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int elem : elements) {
            frequencyMap.put(elem, frequencyMap.getOrDefault(elem, 0) + 1);
        }

        int elementCount = elements.length;
        int[] frequencyCounts = new int[elementCount + 1];

        for (int freq : frequencyMap.values()) {
            frequencyCounts[freq]++;
        }

        int remainUnique = frequencyMap.size();

        for (int freq = 1; freq <= elementCount; freq++) {
            int maxRemove = Math.min(removals / freq, frequencyCounts[freq]);
            removals -= (freq * maxRemove);
            remainUnique -= maxRemove;
            if (removals < freq) {
                return remainUnique;
            }
        }

        return 0;
    }
}

The provided Java code solves the problem of determining the least number of unique integers left in an array after a specified number of removals. The method minUniqueIntegers, defined within the Solution class, takes two parameters: an array of integers elements and an integer removals which specifies how many elements should be removed from the array.

The solution approach involves:

• Using a HashMap to count the frequency of each integer in the elements array.
• Initializing an array frequencyCounts to keep track of how many numbers have the same frequency.
• Iterating through the frequencyMap to populate the frequencyCounts array.
• Calculating the maximum number of integers that can be removed without reducing the number of unique integers below the required level. This is done by iterating through potential frequencies and adjusting removals and remainUnique accordingly.
• Immediately returning the remaining count of unique integers when the number of possible removals is less than the next frequency count.

If all removals can be performed without reducing the number of unique integers to zero, the method finally returns zero, indicating that all integers have been removed.

This solution efficiently handles the modification of the array and return of unique integers based on frequency and removal constraints in linear time complexity relative to the size and content of the input array.

class Solution:
    def findMinUniqueInts(self, nums: List[int], remove_count: int) -> int:
        freq_dict = {}
        for number in nums:
            freq_dict[number] = freq_dict.get(number, 0) + 1

        total_nums = len(nums)
        frequency_counter = [0] * (total_nums + 1)

        for frequency in freq_dict.values():
            frequency_counter[frequency] += 1

        remaining_distinct_elements = len(freq_dict)

        for freq in range(1, total_nums + 1):
            max_removal_count = min(remove_count // freq, frequency_counter[freq])
            remove_count -= (freq * max_removal_count)
            remaining_distinct_elements -= max_removal_count

            if remove_count < freq:
                return remaining_distinct_elements

        return 0

The given Python code defines a class Solution with a method findMinUniqueInts that calculates the least number of unique integers left in an array after removing a specified number of elements. Follow the below explanation to understand the approach taken in the code:

• Start by creating a frequency dictionary, freq_dict, which maps each integer in the input list nums to its occurrence count.
• Initialize a list frequency_counter with zeros to count how many numbers have the same frequency, indexed by their respective frequencies.
• Populate the frequency_counter using the values in freq_dict, and determine the initial number of unique elements as remaining_distinct_elements.
• Step through each potential frequency, determining the maximum number of unique integers that can be removed given the current remove_count and the frequency of integers (frequency_counter). Update the remaining_distinct_elements accordingly.
• Reduce remove_count for each operation. If remove_count becomes less than the frequency of the next group of integers to consider, return the current count of remaining_distinct_elements.
• Should all numbers be removable within the limit, return 0.

This methodology ensures efficient management of removals and checks with respect to the provided constraints, ultimately determining the minimum number of unique integers left. The use of a frequency dictionary and indexing array maximizes efficiency, making the approach suitable for large inputs.