Least Number of Unique Integers after K Removals
Problem
Given an integer array arr and an integer k, remove exactly k elements from the array such that the number of unique integers remaining is minimized, and return this minimum number of unique integers.
- 1 ≤ arr.length ≤ 10⁵
- 1 ≤ arr[i] ≤ 10⁹
- 1 ≤ k ≤ arr.length
Example
arr = [5,5,4], k = 11The frequency counts are {5: 2, 4: 1}. Removing one element from the integer with the smallest frequency (4) removes it entirely, leaving only one unique integer (5). This is the minimal number of unique integers achievable after removing k=1 elements.
Approach
Straightforward Solution
A brute-force approach would try all combinations of removing k elements, which is combinatorially explosive and infeasible for large arrays.
Core Observation
The minimal number of unique integers after removing k elements is achieved by removing entire integers with the smallest frequencies first, because removing all occurrences of a low-frequency integer reduces the unique count by one at the least cost.
Path to Optimal
The key insight is to count the frequencies of each integer, then sort these frequencies in ascending order. Removing integers with the smallest frequencies first uses the fewest removals to reduce the unique count. Iteratively subtract frequencies from k until k is exhausted or no more integers can be fully removed. The remaining unique integers are those not fully removed.
Optimal Approach
Count frequencies using a hash map, sort the frequency values ascendingly, then greedily remove integers starting from the smallest frequency by subtracting their counts from k. Stop when k is less than the next frequency. The answer is the total unique integers minus the count of fully removed integers.
Time
O(n log n)
Counting frequencies takes O(n). Sorting the frequency list takes O(m log m), where m is the number of unique integers, which is at most n. The while loop iterates at most m times, so total complexity is dominated by sorting.
Space
O(n)
The frequency map stores counts for up to n unique integers in the worst case, requiring O(n) auxiliary space.
Pattern Spotlight
Greedy Algorithms (Frequency-Based Removal)
When minimizing the count of unique elements after removals, always remove entire elements with the smallest frequencies first, as this yields the greatest reduction in unique count per removal cost.
Solution
| 1 | from collections import Counter
|
| 2 |
|
| 3 | class Solution:
|
| 4 | def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
|
| 5 | counts = Counter(arr)
|
| 6 | freqs = sorted(counts.values())
|
| 7 |
|
| 8 | i = 0
|
| 9 | while i < len(freqs) and k >= freqs[i]:
|
| 10 | k -= freqs[i]
|
| 11 | i += 1
|
| 12 |
|
| 13 | return len(freqs) - i |
Step-by-Step Solution
Count Frequencies of Each Integer in the Array
| 5 | counts = Counter(arr)
|
Objective
To build a frequency map that records how many times each integer appears in the array.
Key Insight
Knowing the frequency of each integer is essential because the cost to remove an integer entirely equals its frequency. This frequency map enables the greedy strategy to prioritize removals of integers with the smallest counts first.
Interview Quick-Check
Core Logic
Counting frequencies transforms the problem from element-level removals to frequency-level removals, enabling efficient greedy decisions.
Complexity
Frequency counting is O(n) time and O(n) space, where n is the array length.
Sort Frequencies to Prioritize Removal of Least Frequent Integers
| 6 | freqs = sorted(counts.values())
|
Objective
To order the frequency counts in ascending order so that integers with the smallest frequencies can be removed first.
Key Insight
Sorting frequencies allows the algorithm to greedily remove entire integers starting from those that require the fewest removals, maximizing the reduction in unique integers per unit of k spent.
Interview Quick-Check
Core Logic
Sorting frequencies enables a linear scan to remove integers in order of increasing cost, which is the essence of the greedy approach.
Complexity
Sorting takes O(m log m) time, where m is the number of unique integers.
Common Pitfalls & Bugs
A common mistake is sorting the integers themselves instead of their frequencies. The greedy order depends only on how many times an integer appears, not on its numeric value.
Greedily Remove Integers Starting from the Smallest Frequency
| 8 | i = 0
|
| 9 | while i < len(freqs) and k >= freqs[i]:
|
| 10 | k -= freqs[i]
|
| 11 | i += 1
|
Objective
To iteratively subtract frequencies from k, removing entire integers until k is exhausted or no more integers can be fully removed.
Key Insight
By removing integers with the smallest frequencies first, the algorithm uses the limited removal budget k most efficiently to reduce the unique count. The loop stops when k is insufficient to remove the next integer entirely, ensuring no partial removals that don't reduce unique count.
Interview Quick-Check
Core Logic
The loop removes entire integers by subtracting their frequency from k, counting how many unique integers are fully removed.
State & Boundaries
The loop condition ensures that only integers whose frequency is less than or equal to the remaining k are removed.
Common Pitfalls & Bugs
Failing to check k >= freqs[i] before removal can lead to incorrect partial removals that don't reduce unique count.
Calculate and Return the Remaining Number of Unique Integers
| 13 | return len(freqs) - i |
Objective
To compute the final count of unique integers remaining after removals and return it.
Key Insight
The remaining unique integers equal the total unique integers minus the count of fully removed integers. This calculation directly reflects the problem's goal.
Interview Quick-Check
Core Logic
Subtracting the count of fully removed integers from the total unique count yields the minimal unique integers after k removals.
Line Analysis
This solution has 1 Critical line interviewers watch for.
while i < len(freqs) and k >= freqs[i]:Check if the current integer's frequency can be fully removed within the remaining k.
This conditional check is critical because removing an integer only reduces the unique count if all its occurrences are removed; partial removals do not reduce the unique count and would violate the problem constraints.
counts = Counter(arr)Count the frequency of each integer in the array using a hash map.
This frequency map is the foundation for the greedy strategy, enabling the algorithm to prioritize removals based on integer occurrence counts.
freqs = sorted(counts.values())Sort the frequency values in ascending order.
Sorting frequencies allows the algorithm to efficiently remove integers starting from those with the smallest counts, maximizing unique integer reduction per removal.
return len(freqs) - iReturn the number of unique integers remaining after removals.
Subtracting the count of fully removed integers from the total unique count yields the minimal unique integers achievable after k removals, which is the problem's required output.
k -= freqs[i]Subtract the current integer's frequency from k to account for removals.
This updates the remaining removal budget, reflecting the cost of removing the entire integer.
i += 1Increment the count of fully removed integers.
Tracking the number of fully removed integers is essential to compute the final number of unique integers remaining.
i = 0Initialize the index to track how many integers have been fully removed.
This index counts how many integers have been removed entirely, which will be used to calculate the final answer.
Test Your Understanding
Why does removing integers with the smallest frequencies first minimize the number of unique integers remaining?
Because removing all occurrences of a low-frequency integer costs fewer removals (k) to reduce the unique count by one, maximizing the reduction in unique integers per removal.
Related Problems
Greedy pattern
Don't just read it. Drill it.
Reconstruct Least Number of Unique Integers after K Removals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Least Number of Unique Integers after K Removals drill