Code Implementation

from collections import Counter

class Solution:
    def findLeastNumOfUniqueInts(self, arr, k):
        freq = Counter(arr)
        counts = sorted(freq.values())
        unique = len(counts)
        for count in counts:
            if k >= count:
                k -= count
                unique -= 1
            else:
                break
        return unique
      

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

class Solution {
public:
    int findLeastNumOfUniqueInts(std::vector<int>& arr, int k) {
        std::unordered_map<int, int> freq;
        for (int num : arr) freq[num]++;
        std::vector<int> counts;
        for (auto& kv : freq) counts.push_back(kv.second);
        std::sort(counts.begin(), counts.end());
        int unique = counts.size();
        for (int count : counts) {
            if (k >= count) {
                k -= count;
                unique--;
            } else {
                break;
            }
        }
        return unique;
    }
};
      

import java.util.*;

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) freq.put(num, freq.getOrDefault(num, 0) + 1);
        List<Integer> counts = new ArrayList<>(freq.values());
        Collections.sort(counts);
        int unique = counts.size();
        for (int count : counts) {
            if (k >= count) {
                k -= count;
                unique--;
            } else {
                break;
            }
        }
        return unique;
    }
}
      

var findLeastNumOfUniqueInts = function(arr, k) {
    const freq = {};
    for (const num of arr) freq[num] = (freq[num] || 0) + 1;
    const counts = Object.values(freq).sort((a, b) => a - b);
    let unique = counts.length;
    for (const count of counts) {
        if (k >= count) {
            k -= count;
            unique--;
        } else {
            break;
        }
    }
    return unique;
};
      

Problem Description

You are given an array arr of integers and an integer k. Your task is to remove exactly k elements from arr (removals can be from anywhere in the array, and the same value can be removed multiple times if it appears multiple times), so that the number of unique integers left in arr is minimized.

Return the least number of unique integers that remain after exactly k removals.

• Each removal deletes a single element from the array.
• You must perform exactly k removals.
• There is always at least one valid way to remove k elements.
• Do not reuse removed elements.

Thought Process

At first glance, you might consider trying to remove elements in a brute-force way: try every combination of k elements to remove, and count the number of unique integers left. However, this is computationally infeasible for large arrays, since the number of possible combinations is enormous.

To optimize, we need to focus on removing entire occurrences of numbers that appear the least. If a number appears only once, removing it will decrease the unique count by one. If it appears multiple times, removing all its occurrences will also reduce the unique count by one, but it costs more removals. So, to minimize unique integers, we should prioritize removing numbers with the fewest occurrences, as they cost the least (in terms of removals) to eliminate from the unique count.

This leads us to a greedy approach: always remove the number with the smallest frequency first, and keep doing this until we've used up k removals.

Solution Approach

• Step 1: Count how many times each number appears in arr. This can be done with a hash map or dictionary.
• Step 2: Collect all the frequencies (the counts of each unique number) into a list.
• Step 3: Sort the list of frequencies in ascending order. This way, the numbers that are easiest to completely remove (those with the lowest frequency) come first.
• Step 4: Iterate through the sorted frequencies:
  • For each frequency f, if k is greater than or equal to f, subtract f from k and reduce the count of unique numbers by 1 (since you've removed all occurrences of that number).
  • If k is less than f, you can't remove all occurrences of this number, so stop the process.
• Step 5: Return the number of unique integers remaining.

We use a hash map/dictionary for fast lookups and counting, and sorting to efficiently prioritize which numbers to remove.

Example Walkthrough

Sample Input: arr = [4,3,1,1,3,3,2], k = 3

1. Count frequencies:
   • 4: 1
   • 3: 3
   • 1: 2
   • 2: 1
2. Frequencies list: [1, 1, 2, 3] (for 4, 2, 1, 3)
3. Sort frequencies: [1, 1, 2, 3]
4. Start with 4 unique numbers.
5. First frequency is 1 (number 4): Remove it (k=3-1=2), unique=3.
6. Next frequency is 1 (number 2): Remove it (k=2-1=1), unique=2.
7. Next frequency is 2 (number 1): Only 1 removal left, can't remove all occurrences, so stop.
8. Result: 2 unique integers remain (numbers 1 and 3).

Time and Space Complexity

• Brute-force approach: Would require checking all possible ways to remove k elements, which is O(C(n, k)) combinations—clearly infeasible for large n.
• Optimized approach:
  • Counting frequencies: O(n), where n is the length of arr.
  • Sorting frequencies: O(u \log u), where u is the number of unique integers.
  • Iterating through frequencies: O(u).
  • Total time complexity: O(n + u \log u)
  • Space complexity: O(u) for storing the frequency map and the counts array.

Summary

The key insight is to remove numbers with the fewest occurrences first, since this reduces the unique count most efficiently for each removal spent. By counting frequencies, sorting them, and greedily removing the lowest-frequency numbers, we guarantee the minimum number of unique integers remain after exactly k removals. This approach is both elegant and efficient, using common data structures and sorting.