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); 
                list.add(arr[i]); 
            } 
            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; 
    } 
}