#1481 Least Unique Integers K Removals - Solution

Dashboard Questions Topics Companies Sheets

The key idea in #1481 Least Number of Unique Integers after K Removals is to remove elements in a way that minimizes the number of distinct values left in the array. Instead of removing elements arbitrarily, first compute the frequency of each integer using a hash map. Each frequency tells us how many deletions are required to eliminate that integer completely.

Once frequencies are known, apply a greedy strategy: remove integers with the smallest frequency first. This can be done by sorting the frequency list or by using a min-heap. Repeatedly subtract the smallest frequency from k (the allowed removals). Every time you fully remove a number's occurrences, the total count of unique integers decreases.

Stop when k is no longer sufficient to remove the next frequency. The remaining frequencies correspond to the number of unique integers left in the array. This strategy works because removing smaller groups first maximizes the reduction in unique values. The dominant cost comes from sorting or heap operations.

Approach	Time Complexity	Space Complexity
Hash Map + Sorting Frequencies (Greedy)	O(n log n)	O(n)
Hash Map + Min Heap	O(n log n)	O(n)

Solutions (12)

Approach with Frequency Count and Min-Heap

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.

Time Complexity: O(n log n) due to sorting the frequency array. Space Complexity: O(n) for storing the frequency counts.

C C++Java Python C#JavaScript

1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {

Explanation

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.

Greedy Approach with Frequency Counting

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.

Time Complexity: O(n log n) due to the qsort on frequencies. Space Complexity: O(n) for arrays used in frequency counting.

C C++Java Python C#JavaScript

1#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;

int leastNumberOfUniqueInts(vector<int>& arr, int k) {
    unordered_map<int, int> count;
    for (int num : arr) {
        count[num]++;
    }

    vector<int> frequencies;
    for (auto& kvp : count) {
        frequencies.push_back(kvp.second);
    }

    sort(frequencies.begin(), frequencies.end());

    int unique = frequencies.size();
    for (int freq : frequencies) {
        if (k >= freq) {
            k -= freq;
            unique--;
        } else {
            break;
        }
    }

    return unique;
}

int main() {
    vector<int> arr = {5, 5, 4};
    int k = 1;
    cout << leastNumberOfUniqueInts(arr, k) << endl;
    return 0;
}