# Least Number of Unique Integers after K Removals
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals)
Canonical: https://scaleengineer.com/dsa/problems/least-number-of-unique-integers-after-k-removals
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [IBM](https://scaleengineer.com/companies/ibm), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan)
---
## Problem
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^5`
* `1 <= arr[i] <= 10^9`
* `0 <= k <= arr.length`

# Approaches
## Hash Map and Sorting
This approach first calculates the frequency of each number in the input array and then sorts these frequencies. By sorting the frequencies in ascending order, we can greedily remove the numbers that appear least often to minimize the number of unique integers.
**Time:** O(N + U log U), where N is the number of elements in `arr` and U is the number of unique elements. O(N) to build the frequency map. O(U log U) to sort the frequencies. O(U) to iterate through the frequencies. The sorting step dominates. · **Space:** O(U), for the `HashMap` and the list of frequencies, where U is the number of unique elements. In the worst case, where all elements are unique, this becomes O(N).
**Pros:** Relatively simple to understand and implement.; Works correctly for all cases.
**Cons:** The sorting step (O(U log U)) is not the most optimal, especially when the number of unique elements U is large.
### Explanation
The core idea is that to reduce the count of unique integers most effectively, we should remove elements that form the smallest frequency groups.
1.  **Frequency Counting:** We traverse the input array `arr` and use a `HashMap` to store the count of each integer. The keys of the map will be the unique numbers, and the values will be their frequencies.
2.  **Extract and Sort Frequencies:** We extract all the frequency values from the `HashMap` into a list. Then, we sort this list in ascending order. This places the counts of the rarest elements at the beginning of the list.
3.  **Greedy Removal:** We initialize a variable `uniqueCount` to the total number of unique elements (the size of the map). We then iterate through the sorted frequencies. For each frequency `f`, we check if we have enough `k` removals left to remove all occurrences of an element with that frequency.
    *   If `k >= f`, we perform the removal by subtracting `f` from `k` and decrementing `uniqueCount`.
    *   If `k < f`, we don't have enough removals to eliminate this entire group of numbers (or any subsequent, larger groups). We stop the process here.
4.  **Result:** The final value of `uniqueCount` is the minimum number of unique integers remaining.
```java
import java.util.*;

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        // 1. Count frequencies of each number
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 2. Extract frequencies into a list
        List<Integer> frequencies = new ArrayList<>(freqMap.values());

        // 3. Sort the frequencies in ascending order
        Collections.sort(frequencies);

        // 4. Iterate and remove elements
        int uniqueCount = frequencies.size();
        for (int freq : frequencies) {
            if (k >= freq) {
                k -= freq;
                uniqueCount--;
            } else {
                // Not enough k to remove this entire group
                break;
            }
        }
        return uniqueCount;
    }
}
```
### Algorithm
*   Create a `HashMap` to store the frequency of each integer in `arr`.
*   Create a `List` and populate it with the frequency values from the `HashMap`.
*   Sort the list of frequencies in non-decreasing order.
*   Initialize `uniqueCount` to the initial number of unique integers (the size of the list).
*   Iterate through the sorted frequencies. For each frequency `f`:
    *   If `k` is greater than or equal to `f`, subtract `f` from `k` and decrement `uniqueCount`.
    *   Otherwise, break the loop.
*   Return `uniqueCount`.

## Hash Map and Min-Heap (Priority Queue)
This approach improves upon sorting by using a Min-Heap (Priority Queue) to efficiently access the smallest frequency at each step. Instead of sorting all frequencies at once, we process them one by one, always picking the smallest available.
**Time:** O(N + U log U), where N is the length of `arr` and U is the number of unique elements. O(N) for frequency counting. O(U log U) to build the heap by inserting U elements. O(k' log U) for removals, where k' is the number of groups removed. In the worst case, this is O(U log U). The total complexity is dominated by building and processing the heap. · **Space:** O(U), for the `HashMap` and the `PriorityQueue`, where U is the number of unique elements. In the worst case, O(N).
**Pros:** Conceptually clean, always processing the next smallest element.; Can be more efficient than full sorting if `k` is very small, as we don't need to process the entire heap.
**Cons:** Has the same worst-case time complexity as the sorting approach.; Slightly more overhead due to the heap data structure compared to a simple array/list sort.
### Explanation
Similar to the sorting approach, we first need to count the frequencies. However, instead of sorting them all, we use a data structure that keeps them ordered dynamically.
1.  **Frequency Counting:** Use a `HashMap` to count the occurrences of each number in `arr`.
2.  **Build Min-Heap:** Create a `PriorityQueue` (which acts as a Min-Heap in Java) and insert all the frequency values from the `HashMap` into it. The heap will automatically maintain the smallest frequency at its root.
3.  **Greedy Removal:** While `k` is greater than 0 and the heap is not empty, we repeatedly check the smallest frequency (the top of the heap).
    *   If `k` is greater than or equal to the smallest frequency, we can remove that group of elements. We `poll` the frequency from the heap and subtract its value from `k`.
    *   If `k` is smaller than the smallest frequency, we cannot remove any more full groups, so we stop.
4.  **Result:** The number of elements remaining in the heap is the least number of unique integers after the removals.
```java
import java.util.*;

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        // 1. Count frequencies of each number
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // 2. Build a Min-Heap of frequencies
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(freqMap.values());

        // 3. Greedily remove from the heap
        while (k > 0 && !minHeap.isEmpty()) {
            int smallestFreq = minHeap.peek();
            if (k >= smallestFreq) {
                k -= smallestFreq;
                minHeap.poll();
            } else {
                break;
            }
        }

        // 4. The size of the heap is the number of unique integers left
        return minHeap.size();
    }
}
```
### Algorithm
*   Create a `HashMap` to store the frequency of each integer in `arr`.
*   Create a `PriorityQueue` (Min-Heap) and add all the frequency values from the `HashMap` to it.
*   While `k > 0` and the heap is not empty:
    *   Get the smallest frequency `f` from the heap's top.
    *   If `k` is greater than or equal to `f`, subtract `f` from `k` and remove the element from the heap.
    *   Otherwise, break the loop.
*   Return the final size of the heap.

## Hash Map and Bucket Sort
This is the most optimal approach, achieving linear time complexity. It leverages the fact that frequencies are integers within a known range. Instead of a comparison-based sort, we use a form of counting sort (or bucket sort) to group numbers by their frequency.
**Time:** O(N), where N is the length of `arr`. O(N) to build the frequency map. O(U) to populate the buckets, where U is the number of unique elements (U <= N). O(N) to iterate through the buckets array. The overall complexity is linear. · **Space:** O(N), for the `HashMap` (up to O(U)) and the `buckets` array (size N+1). In the worst case, O(N).
**Pros:** Most efficient solution with linear time complexity.; Avoids comparison-based sorting.
**Cons:** Requires extra space proportional to N for the bucket array, which might be large if N is large, even if the number of unique elements U is small.
### Explanation
This method avoids the O(U log U) sorting bottleneck by using an array to act as buckets for frequencies.
1.  **Frequency Counting:** As before, use a `HashMap` to count the frequency of each number in `arr`.
2.  **Bucket Frequencies:** Create an array, `buckets`, of size `arr.length + 1`. `buckets[i]` will store the *count of numbers* that have a frequency of `i`. We iterate through the frequencies in our `HashMap` and for each frequency `f`, we increment `buckets[f]`.
3.  **Greedy Removal from Buckets:** We iterate through the `buckets` array from the smallest frequency `i = 1` upwards. Let `uniqueCount` be the initial number of unique elements.
    *   For each frequency `i`, we know there are `buckets[i]` unique numbers that appear `i` times.
    *   If we have enough `k` to remove all these groups (i.e., `k >= i * buckets[i]`), we do so by updating `k` and decrementing `uniqueCount` by `buckets[i]`.
    *   If we don't have enough `k`, we calculate how many full groups we *can* remove (`k / i`), subtract that from `uniqueCount`, and return immediately, as we can't remove any more groups.
4.  **Result:** The final `uniqueCount` is the answer.
```java
import java.util.*;

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        // 1. Count frequencies of each number
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        int uniqueCount = freqMap.size();

        // 2. Bucket the frequencies. buckets[i] = count of numbers with frequency i
        int[] buckets = new int[arr.length + 1];
        for (int freq : freqMap.values()) {
            buckets[freq]++;
        }

        // 3. Iterate through buckets and remove
        for (int i = 1; i < buckets.length; i++) {
            // i is the frequency
            // buckets[i] is the number of elements with this frequency
            if (buckets[i] > 0) {
                int numElementsToRemove = i * buckets[i];
                if (k >= numElementsToRemove) {
                    k -= numElementsToRemove;
                    uniqueCount -= buckets[i];
                } else {
                    // Cannot remove all elements with this frequency.
                    // Remove as many full groups as possible.
                    int numGroupsToRemove = k / i;
                    uniqueCount -= numGroupsToRemove;
                    // We have used up our k, so we are done.
                    return uniqueCount;
                }
            }
        }
        return uniqueCount;
    }
}
```
### Algorithm
*   Create a `HashMap` to store the frequency of each integer in `arr`.
*   Initialize `uniqueCount` to the size of the `HashMap`.
*   Create a `buckets` array of size `arr.length + 1`.
*   Iterate through the frequencies in the `HashMap`. For each frequency `f`, increment `buckets[f]`.
*   Iterate through the `buckets` array from frequency `i = 1` to `arr.length`.
*   Let `countOfNumbers` be `buckets[i]`. If it's greater than 0:
    *   Calculate the total elements to remove for this frequency: `cost = i * countOfNumbers`.
    *   If `k >= cost`, subtract `cost` from `k` and `countOfNumbers` from `uniqueCount`.
    *   Otherwise, calculate how many full groups can be removed: `groupsToRemove = k / i`. Subtract `groupsToRemove` from `uniqueCount` and return the result.
*   If the loop completes, return `uniqueCount` (which would be 0 if k was large enough).

# Solutions
### Java

```java
class Solution { public int findLeastNumOfUniqueInts ( int [] arr , int k ) { Map < Integer , Integer > cnt = new HashMap <>(); for ( int x : arr ) { cnt . merge ( x , 1 , Integer: : sum ); } List < Integer > nums = new ArrayList <>( cnt . values ()); Collections . sort ( nums ); for ( int i = 0 , m = nums . size (); i < m ; ++ i ) { k -= nums . get ( i ); if ( k < 0 ) { return m - i ; } } return 0 ; } }
```

### CPP

```cpp
class Solution { public: int findLeastNumOfUniqueInts ( vector < int >& arr , int k ) { unordered_map < int , int > cnt ; for ( int & x : arr ) { ++ cnt [ x ]; } vector < int > nums ; for ( auto & [ _ , c ] : cnt ) { nums . push_back ( c ); } sort ( nums . begin (), nums . end ()); for ( int i = 0 , m = nums . size (); i < m ; ++ i ) { k -= nums [ i ]; if ( k < 0 ) { return m - i ; } } return 0 ; } };
```

### Python

```python
class Solution : def findLeastNumOfUniqueInts ( self , arr : List [ int ], k : int ) -> int : cnt = Counter ( arr ) for i , v in enumerate ( sorted ( cnt . values ())): k -= v if k < 0 : return len ( cnt ) - i return 0
```