Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.
Example 1:
Input: arr = [5,5,4], k = 1 Output: 1 Explanation: Remove the single 4, only 5 is left.Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3 Output: 2 Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
Constraints:
1 <= arr.length <= 10^51 <= arr[i] <= 10^90 <= k <= arr.lengthProblem Overview: You receive an integer array and an integer k. Remove exactly k elements so the number of distinct integers left in the array is as small as possible. The key observation: removing numbers that appear fewer times eliminates unique values faster than removing frequent numbers.
Approach 1: Frequency Count + Min-Heap (O(n + m log m) time, O(m) space)
Start by counting how many times each value appears using a hash map. This transforms the problem into managing frequencies instead of raw elements. Push all frequencies into a min-heap so the smallest counts come first. Repeatedly pop the smallest frequency and subtract it from k. If k is large enough to remove all occurrences of that number, you eliminate one unique integer. Continue until k is exhausted. The heap ensures you always remove the cheapest unique number first. Time complexity is O(n + m log m) where m is the number of distinct integers, and space complexity is O(m). This approach combines hash table counting with a priority queue for optimal removal order.
Approach 2: Greedy Frequency Counting with Sorting (O(n + m log m) time, O(m) space)
Instead of a heap, store the frequency counts in a list and sort them in ascending order. This produces the same removal order as the heap but uses sorting once instead of repeated heap operations. Iterate through the sorted frequencies. For each frequency f, check if k ≥ f. If true, remove all occurrences and reduce k by f, which eliminates one unique number. Once k becomes smaller than the next frequency, you stop because removing that number completely is impossible. The remaining count of frequencies gives the number of unique integers left. This greedy strategy works because removing smaller groups always yields the maximum reduction in unique values. Complexity is O(n + m log m) time and O(m) space due to the frequency map and sorting. This technique highlights classic greedy reasoning combined with sorting.
Recommended for interviews: The greedy frequency approach is what most interviewers expect. Building a frequency map and removing the smallest counts first demonstrates a clear understanding of greedy optimization. The min-heap solution shows stronger familiarity with priority queues and dynamic selection, while the sorted-frequency approach is simpler and often easier to implement quickly during interviews.
This approach involves two main steps. First, count the frequency of each integer in the array. Second, use a min-heap (or priority queue) to remove the integers with the smallest frequency first. This approach ensures that we are removing the least frequent integers to reach the least number of unique integers efficiently.
This C program implements the approach by utilizing an array to keep the frequency of each integer. It then collects these frequencies into another array which is sorted to allow removal of the lowest frequencies first. A loop continues removing these and reducing the count of unique integers. A direct index is maintained to access frequencies in order.
Time Complexity: O(n log n) due to sorting the frequency array. Space Complexity: O(n) for storing the frequency counts.
This approach takes a greedy strategy to count frequencies of integers and sorts them. By progressively removing elements with smallest frequencies, it directly calculates the least number of unique integers remaining after exactly k removals.
This implementation in C uses a frequency array to count each integer's occurrences. After sorting this array, elements are removed from the smallest frequency upwards until k removals are exhausted.
Time Complexity: O(n log n) due to the qsort on frequencies. Space Complexity: O(n) for arrays used in frequency counting.
We use the hash table cnt to count the number of times each integer in the array arr appears, and then sort the values in cnt in ascending order, and record them in the array nums.
Next, we traverse the array nums. For the current value that we traverse to nums[i], we subtract k by nums[i]. If k \lt 0, it means that we have removed k elements, and the minimum number of different integers in the array is the length of nums minus the index i that we traverse to at the current time. Return directly.
If we traverse to the end, it means that we have removed all the elements, and the minimum number of different integers in the array is 0.
The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array arr.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach with Frequency Count and Min-Heap | Time Complexity: O(n log n) due to sorting the frequency array. Space Complexity: O(n) for storing the frequency counts. |
| Greedy Approach with Frequency Counting | Time Complexity: O(n log n) due to the qsort on frequencies. Space Complexity: O(n) for arrays used in frequency counting. |
| Hash Table + Sorting | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count + Min-Heap | O(n + m log m) | O(m) | General case when you want dynamic access to the smallest frequency using a priority queue |
| Greedy Frequency Counting with Sorting | O(n + m log m) | O(m) | Simpler implementation when sorting frequencies once is acceptable |
Least Number of Unique Integers after K Removal - Leetcode 1481 - Python • NeetCodeIO • 12,679 views views
Watch 9 more video solutions →Practice Least Number of Unique Integers after K Removals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor