Least Number of Unique Integers after K Removals

Given an array arr of integers and an integer k, you need to find the least number of unique integers after removing exactly k elements from the array.

Table of Contents

Sample Input and Expected Output:

Input:

arr = [4, 3, 1, 1, 3, 3, 2]
k = 3

Output:

The least number of unique integers after k removals is: 1

Input:

arr = [5, 5, 4]
k = 1

Output:

The least number of unique integers after k removals is: 1

Solution in C++:

The idea is to use a hash map to count the frequency of each element in the array. Then, we sort the elements based on their frequencies. We start removing elements with the lowest frequencies first until we have removed k elements. The remaining unique elements will give us the least number of unique integers.

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

int findLeastNumOfUniqueInts(std::vector<int>& arr, int k) {
    std::unordered_map<int, int> freqMap;

    // Count the frequency of each element in the array.
    for (int num : arr) {
        freqMap[num]++;
    }

    // Create a vector of pairs (number, frequency).
    std::vector<std::pair<int, int>> freqVec(freqMap.begin(), freqMap.end());

    // Sort the vector based on frequencies in ascending order.
    std::sort(freqVec.begin(), freqVec.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
        return a.second < b.second;
    });

    int uniqueCount = freqVec.size();

    // Remove elements with the lowest frequencies first until k removals are done.
    for (const auto& freqPair : freqVec) {
        int frequency = freqPair.second;
        if (k >= frequency) {
            k -= frequency;
            uniqueCount--;
        } else {
            break;
        }
    }

    return uniqueCount;
}

int main() {
    std::vector<int> arr1 = {4, 3, 1, 1, 3, 3, 2};
    std::vector<int> arr2 = {5, 5, 4};
    int k1 = 3;
    int k2 = 1;

    int result1 = findLeastNumOfUniqueInts(arr1, k1);
    int result2 = findLeastNumOfUniqueInts(arr2, k2);

    std::cout << "The least number of unique integers after k removals is: " << result1 << std::endl;
    std::cout << "The least number of unique integers after k removals is: " << result2 << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n log n), where n is the size of the input vector arr. This is because we are first counting the frequency of each element using a hash map, which takes O(n) time. Then, we sort the elements based on their frequencies using std::sort(), which takes O(n log n) time.

The space complexity is O(n) as we are using a hash map to store the frequency of each element, and a vector to store the pairs of numbers and their frequencies. The size of these data structures depends on the number of unique elements in the input array, which can be at most n.

← Sort Array by Increasing Frequency