Scale Engineer

Least Number of Unique Integers after K Removals

Med
#1367Time: O(N + U log U), where N is the number of elements in `arr` and U is the number of unique elements. O(N) to build the frequency map. O(U log U) to sort the frequencies. O(U) to iterate through the frequencies. The sorting step dominates.Space: O(U), for the `HashMap` and the list of frequencies, where U is the number of unique elements. In the worst case, where all elements are unique, this becomes O(N).3 companies
Patterns
GreedyCounting
Algorithms
Sorting
Data structures
ArrayHash Table
Companies
ExpediaIBMJ.P. Morgan

Prompt

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

 

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
Example 2: 
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

 

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • 0 <= k <= arr.length

Approaches

3 approaches with complexity analysis and trade-offs.

This approach first calculates the frequency of each number in the input array and then sorts these frequencies. By sorting the frequencies in ascending order, we can greedily remove the numbers that appear least often to minimize the number of unique integers.

Algorithm

  • Create a HashMap to store the frequency of each integer in arr.
  • Create a List and populate it with the frequency values from the HashMap.
  • Sort the list of frequencies in non-decreasing order.
  • Initialize uniqueCount to the initial number of unique integers (the size of the list).
  • Iterate through the sorted frequencies. For each frequency f:
    • If k is greater than or equal to f, subtract f from k and decrement uniqueCount.
    • Otherwise, break the loop.
  • Return uniqueCount.

Walkthrough

The core idea is that to reduce the count of unique integers most effectively, we should remove elements that form the smallest frequency groups.

  1. Frequency Counting: We traverse the input array arr and use a HashMap to store the count of each integer. The keys of the map will be the unique numbers, and the values will be their frequencies.
  2. Extract and Sort Frequencies: We extract all the frequency values from the HashMap into a list. Then, we sort this list in ascending order. This places the counts of the rarest elements at the beginning of the list.
  3. Greedy Removal: We initialize a variable uniqueCount to the total number of unique elements (the size of the map). We then iterate through the sorted frequencies. For each frequency f, we check if we have enough k removals left to remove all occurrences of an element with that frequency.
    • If k >= f, we perform the removal by subtracting f from k and decrementing uniqueCount.
    • If k < f, we don't have enough removals to eliminate this entire group of numbers (or any subsequent, larger groups). We stop the process here.
  4. Result: The final value of uniqueCount is the minimum number of unique integers remaining.
import java.util.*; class Solution {    public int findLeastNumOfUniqueInts(int[] arr, int k) {        // 1. Count frequencies of each number        Map<Integer, Integer> freqMap = new HashMap<>();        for (int num : arr) {            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);        }         // 2. Extract frequencies into a list        List<Integer> frequencies = new ArrayList<>(freqMap.values());         // 3. Sort the frequencies in ascending order        Collections.sort(frequencies);         // 4. Iterate and remove elements        int uniqueCount = frequencies.size();        for (int freq : frequencies) {            if (k >= freq) {                k -= freq;                uniqueCount--;            } else {                // Not enough k to remove this entire group                break;            }        }        return uniqueCount;    }}

Complexity

Time

O(N + U log U), where N is the number of elements in `arr` and U is the number of unique elements. O(N) to build the frequency map. O(U log U) to sort the frequencies. O(U) to iterate through the frequencies. The sorting step dominates.

Space

O(U), for the `HashMap` and the list of frequencies, where U is the number of unique elements. In the worst case, where all elements are unique, this becomes O(N).

Trade-offs

Pros

  • Relatively simple to understand and implement.

  • Works correctly for all cases.

Cons

  • The sorting step (O(U log U)) is not the most optimal, especially when the number of unique elements U is large.

Solutions

class Solution { public int findLeastNumOfUniqueInts ( int [] arr , int k ) { Map < Integer , Integer > cnt = new HashMap <>(); for ( int x : arr ) { cnt . merge ( x , 1 , Integer: : sum ); } List < Integer > nums = new ArrayList <>( cnt . values ()); Collections . sort ( nums ); for ( int i = 0 , m = nums . size (); i < m ; ++ i ) { k -= nums . get ( i ); if ( k < 0 ) { return m - i ; } } return 0 ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem