LeetCode Solutions Blog

Least Number of Unique Integers after K Removals

Number: 1604

Difficulty: Medium

Paid? No

Problem Description

Given an array of integers arr and an integer k, remove exactly k elements from the array such that the number of unique integers remaining is minimized.

Key Insights

Count the frequency of each integer in arr.
Removing numbers with lower frequency first reduces the number of unique integers effectively.
Use a greedy approach by sorting integer frequencies in ascending order.
Iteratively remove integers completely (if possible) until k removals are exhausted.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the frequency counts, where n is the length of the array.
Space Complexity: O(n) for storing the frequency counts.

Solution

The solution counts the frequency of each integer in the array, then sorts these frequencies in ascending order. By iterating over the sorted frequencies and subtracting from k, we remove integers with lower occurrences first until k becomes insufficient to remove an entire group. The remaining unique integers after these removals yield the least possible count.

Code Solutions

# Python code solution with detailed comments
def findLeastNumOfUniqueInts(arr, k):
    # Count frequency of each integer in the array using a dictionary
    frequency = {}
    for num in arr:
        frequency[num] = frequency.get(num, 0) + 1
    
    # Create a sorted list of frequency values in ascending order
    freq_list = sorted(frequency.values())
    
    # Initialize the count of unique integers
    unique_count = len(freq_list)
    
    # Remove integers starting from the least frequent ones
    for freq in freq_list:
        if k >= freq:
            k -= freq  # Remove all occurrences of this integer
            unique_count -= 1  # One less unique integer remains
        else:
            break  # If k is less than the current frequency, stop removals
            
    return unique_count

# Example usage:
print(findLeastNumOfUniqueInts([4,3,1,1,3,3,2], 3))