# Solution For Least Number Of Unique Integers After K Removals

Problem Statement:
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove the 4, 2 and either one of the two 1s or three 3s. 1 and 2 left.

Solution:
The solution can be obtained using two steps:

1. Count the frequency of all elements in an array and create a dictionary.
2. Sort the dictionary values in non-descending order and remove the first k values.

The rationale behind this solution is that we want to remove the least frequent elements from the array, so that we can preserve as many remaining elements as possible. We create a dictionary to map each unique element to its frequency. We then need to sort the dictionary by its values. We want to maintain the least frequent elements in the array, hence we proceed to remove the k least frequent elements in the array.

Code:

def findLeastNumOfUniqueInts(arr, k):
# Step 1: Create a dictionary that maps each unique element to its frequency
frequency_dict = {}
for element in arr:
if element not in frequency_dict:
frequency_dict[element] = 1
else:
frequency_dict[element] += 1

``````# Step 2: Sort the dictionary by its values and remove the first k elements
sorted_dict = sorted(frequency_dict.items(), key=lambda x:x[1])
count = 0
for i in range(len(sorted_dict)):
count += sorted_dict[i][1]
if count > k:
return len(sorted_dict) - i
return 0
``````

# Test the function

arr1 = [5,5,4] k1 = 1
print(findLeastNumOfUniqueInts(arr1, k1)) # Output: 1

arr2 = [4,3,1,1,3,3,2] k2 = 3
print(findLeastNumOfUniqueInts(arr2, k2)) # Output: 2

# The time complexity of the code is O(nlogn), considering the sorting operation.

## Step by Step Implementation For Least Number Of Unique Integers After K Removals

```import java.util.*;

class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {

// Hashmap to store the frequency of each number
HashMap map = new HashMap<>();

// ArrayList to store all the unique numbers
ArrayList list = new ArrayList<>();

// Loop through the array and store the frequency of each number
for (int i = 0; i < arr.length; i++) {
if (!map.containsKey(arr[i])) {
map.put(arr[i], 1);
}
else {
int count = map.get(arr[i]);
map.put(arr[i], count + 1);
}
}

// Sort the ArrayList in ascending order
Collections.sort(list);

// Variable to keep track of the number of unique integers removed
int removed = 0;

// Loop through the ArrayList
for (int i = 0; i < list.size(); i++) {

// If the number of unique integers removed is equal to k, return the size of the ArrayList
if (removed == k) {
return list.size();
}

// Otherwise, remove the number from the ArrayList and increment the number of unique integers removed
else {
list.remove(i);
removed += map.get(list.get(i));
}
}

// Return 0 if all the unique integers have been removed
return 0;
}
}```
```def findLeastNumOfUniqueInts(nums, k):
if k == 0:
return len(set(nums))

count = collections.Counter(nums)
unique = sorted(count.values())

for i in range(len(unique)):
k -= unique[i]
if k < 0:
return i
return len(unique)```
```/**
* @param {number[]} arr
* @param {number} k
* @return {number}
*/
var findLeastNumOfUniqueInts = function(arr, k) {
// create a map to store the number of times each integer occurs in the array
let map = new Map();
for (let i = 0; i < arr.length; i++) {
if (map.has(arr[i])) {
map.set(arr[i], map.get(arr[i]) + 1);
} else {
map.set(arr[i], 1);
}
}

// convert the map into an array of tuples (integer, number of occurrences)
let tuples = [];
for (let key of map.keys()) {
tuples.push([key, map.get(key)]);
}

// sort the array in ascending order by number of occurrences
tuples.sort((a, b) => a[1] - b[1]);

// remove the first k integers from the array
let count = 0;
for (let i = 0; i < tuples.length; i++) {
if (k >= tuples[i][1]) {
k -= tuples[i][1];
count++;
} else {
break;
}
}

return tuples.length - count;
};```
```There are several ways to approach this problem. One way would be to keep track of the number of unique integers in a data structure, such as a set, as you remove them. You can then return the size of the set after k removals.

another way would be to keep track of the frequencies of each integer in a data structure, such as a map. You can then remove the kth most frequent integer and return the number of unique integers remaining.```
```using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
public int FindLeastNumOfUniqueInts(int[] arr, int k) {

// edge case where k is greater than or equal to the length of the array
if (k >= arr.Length) {
return 0;
}

// create a dictionary to store the number of occurrences of each integer
Dictionary dict = new Dictionary();
foreach (int n in arr) {
if (dict.ContainsKey(n)) {
dict[n]++;
}
else {
dict[n] = 1;
}
}

// create a list of the dictionary keys sorted by the number of occurrences
List list = dict.Keys.ToList();
list.Sort((a, b) => dict[a].CompareTo(dict[b]));

// remove the first k integers from the list
list.RemoveRange(0, k);

// return the number of remaining unique integers
return list.Count;
}
}```

Scroll to Top

## Top 100 Leetcode Practice Problems In Java

Get 30% Off Instantly!
[gravityforms id="5" description="false" titla="false" ajax="true"]