Least Number of Unique Integers after K Removals Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Expedia Facebook Oracle Salesforce
Booking.comViews 3790

Problem Statement

The Least Number of Unique Integers after K Removals LeetCode Solution – “Least Number of Unique Integers after K removals” states that you’re given an array of integers and an integer k. Find the least number of unique integers after removing exactly k elements.

Example:

Least Number of Unique Integers after K Removals Leetcode Solution

 

Input:  arr = [5,5,4], k = 1
Output: 1

Explanation:

  • Since k = 1, we will remove exactly 1 element.
  • Removing a single 5 will give the array as [5,4]. So a number of unique elements are 2.
  • Removing a single 4 will give the array as [5,5]. So a number of unique elements are 1.
  • Hence, removing 4 is optimal since it yields a minimum number of unique elements which is 1.
  • The answer is 1.
Input:  arr = [4,3,1,1,3,3,2], k = 3
Output: 2

Explanation:

  • Since k = 3 we will remove exactly three elements from the input array such that a number of unique elements will be minimized.
  • We can easily observe that removing [4,2,1] will give exactly 2 distinct elements which is the minimum answer possible.

Approach

Idea:

  1. The main idea to solve this problem efficiently is to use (Greedy Approach).
  2. Store all the unique elements frequencies of the given array in the frequency table.
  3. Since we have to minimize the number of distinct elements after removing k elements so, we’ll start from those elements which have a minimum frequency in the given array.
  4. Hence, we need to sort the unique elements and their frequencies in non-decreasing order of their frequencies.
  5. Start with the elements which have minimum frequency and decrease the value of K with the minimum frequency and discard the current element. Repeat the same step till k is positive.
  6. A number of distinct elements that are left after the above operations are done repeatedly till k is positive, is our answer.

Code

C++ Least Number of Unique Integers after K removals String Leetcode Solution:

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int,int> freq;
        for(auto& num:arr){
            freq[num]++;
        }
        vector<pair<int,int>> store;
        for(auto& x:freq){
            store.push_back({x.second,x.first});
        }
        sort(store.rbegin(),store.rend());
        while(k>0){
            int required = min(k,store.back().first);
            k-=required;
            store.back().first-=required;
            
            if(!store.back().first){
                store.pop_back();
            }
        }
        return store.size();
    }
};

 

Java Least Number of Unique Integers after K removals Leetcode Solution:

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int a : arr){
            freq.put(a, 1 + freq.getOrDefault(a, 0));
        }
        int len = freq.size();
        TreeMap<Integer, Integer> occ = new TreeMap<>();
        for (int v : freq.values()){
            occ.put(v, 1 + occ.getOrDefault(v, 0));
        }
        while(k>0){
            Map.Entry<Integer,Integer> entry = occ.pollFirstEntry();
            if(k-entry.getKey()*entry.getValue()>=0){
                k -= entry.getKey()*entry.getValue();
                len -= entry.getValue();
            }
            else{
                return len - k / entry.getKey();
            }
        }
        return len;
    }
}

Complexity Analysis for Least Number of Unique Integers after K removals Leetcode Solution

Time Complexity

The time complexity of the above code is O(N + MlogM + K) where N = length of the input array and M = number of unique elements.

Space Complexity

The space complexity of the above code is O(M), where M = number of unique elements in the input array.

Translate »