Coding Interview PatternsLeast Number of Unique Integers after K Removals
MediumTop K Elements
Least Number of Unique Integers after K Removals
Explanation & Solution
Description
Given an array of integers arr and an integer k, find the least number of unique integers after removing exactly k elements from the array.
You may remove any k elements — they do not need to be contiguous.
Input:arr = [5, 5, 4], k = 1
0
5
1
5
2
4
Output: 1
Explanation: Remove one occurrence of 4, leaving [5, 5] which has 1 unique integer.
Constraints
1 <= arr.length <= 10^51 <= arr[i] <= 10^90 <= k <= arr.length
Approach
Top K Elements pattern
1. Count Frequencies
- Build a frequency map of every integer in
arr. - For example,
[4, 3, 1, 1, 3, 3, 2]produces{4:1, 3:3, 1:2, 2:1}.
2. Sort Frequencies in Ascending Order
- Extract the frequency values and sort them:
[1, 1, 2, 3]. - Sorting in ascending order lets us target the least frequent integers first, which is the greedy strategy to eliminate the most unique values with the fewest removals.
3. Greedily Remove Least Frequent Elements
- Iterate through the sorted frequencies.
- For each frequency, check if we have enough remaining removals (
k) to completely eliminate that integer. - If
k >= frequency, subtract the frequency fromkand count one more unique integer as removed. - If
k < frequency, we cannot fully remove this integer, so we stop.
4. Return the Result
- The answer is the total number of unique integers minus the number we fully removed.
result = totalUnique - removed.
Key Insight
- The greedy approach works because removing all occurrences of a low-frequency integer costs fewer removals than a high-frequency one, so we always eliminate the cheapest unique integers first to minimize the remaining count.
Time
O(n log n)building the frequency map is O(n), and sorting the frequencies is O(n log n) in the worst case.Space
O(n)for the frequency map and sorted array.Visualization
Input:
[5, 5, 4], k = 1
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps