Problem Breakdown
We need to minimize the number of unique integers remaining after removing exactly k elements. To achieve this, we should prioritize eliminating entire groups of identical numbers that appear least frequently first. Removing a single instance of a high-frequency number does not reduce the count of unique integers until all instances are removed. Therefore, the optimal strategy is greedy: exhaustively remove frequencies starting from the smallest counts to maximize the reduction in distinct types per removal cost k.
Intuition
The core insight relies on the Greedy Choice Property. We want to minimize the count of unique integers (distinct values), not just reduce the total array size. Removing an element with frequency 1 reduces our unique count immediately, whereas removing from a high-frequency number does not until that specific value is exhausted entirely. Since we have a fixed budget k, eliminating low-frequency groups first maximizes the reduction in unique types per unit cost of removals.
Approach
- Frequency Counting: Use a hash map (
collections.Counter) to count occurrences of every integer inarr. This handles large values () efficiently without array indexing issues, storing only entries where is the number of unique elements. - Sort Frequencies: Extract just the frequency counts into a list and sort them in ascending order. We want to process numbers that appear least often first because they are “cheaper” to eliminate completely from our unique count perspective.
- Greedy Removal Simulation: Iterate through the sorted frequencies:
- If
kis greater than or equal to the current frequency, we can remove all instances of this number. Subtract its frequency fromk, increment a counter for removed unique integers (or decrement total distinct count), and proceed. - If
kis less than the current frequency, we cannot fully eliminate this integer type with our remaining budget. Since the list is sorted ascendingly, all subsequent frequencies will be greater or equal to the current one. Thus, no further unique integers can be completely removed. We stop here.
- If
- Result Calculation: Return the total number of distinct elements minus those we successfully eliminated in step 3.
Complexity Analysis
- Time Complexity: or more precisely . Counting frequencies takes where is array length (). Sorting the unique counts (where is number of distinct elements, ) takes . Iterating through sorted list is . In worst case (all unique), this becomes , which fits well within time limits for FAANG interviews.
- Space Complexity: or to store the frequency map and the sorted list of counts.
Solution
from collections import Counter
from typing import List
def findLeastNumOfUniqueInts(arr: List[int], k: int) -> int:
# Count frequencies for each unique integer in arr
freq_map = Counter(arr)
# Extract just the frequency counts and sort them ascending.
# We want to eliminate numbers with lowest occurrence first (greedy).
sorted_freqs = sorted(freq_map.values())
removed_unique_count = 0
for count in sorted_freqs:
if k >= count:
# If we can remove all instances of this number, do so.
k -= count
removed_unique_count += 1
else:
# Cannot fully eliminate this number or any subsequent ones
# (since they have equal or higher frequency).
break
return len(sorted_freqs) - removed_unique_count
# Example usage matching problem description logic implicitly handled above.
Edge Cases Handled
k = 0: The loop conditionif k >= countwill fail immediately (unless counts are 0 which is impossible for existing elements), resulting in returning the total distinct count, which is correct as no removals occur.- All Elements Same (
arr=[2,2,2]): Frequency list has one entry3. Ifk >= 3, unique count becomes 0; else it remains 1. Logic holds. kcovers all elements: The loop completes successfully for every frequency in the sorted list.removed_unique_countequals total distinct, returning 0. Correct.- Empty Array (Constraint violation): Constraints state length , but if it were empty,
Counterreturns empty dict, code would return 0 correctly.