Domain 2MediumMEDIUM

Least Number of Unique Integers after K Removals

Count frequencies of all elements using a hash map, then sort these frequencies in ascending order. Greedily subtract the smallest frequencies from k until removals are exhausted or no more full groups can be removed.

Domain: medium•Updated: 2026-09-17
#Greedy#Counter/Hash Map#O(N log N)#O(M)

Problem Breakdown

We need to minimize the number of unique integers remaining after removing exactly k elements. To achieve this, we should prioritize eliminating entire groups of identical numbers that appear least frequently first. Removing a single instance of a high-frequency number does not reduce the count of unique integers until all instances are removed. Therefore, the optimal strategy is greedy: exhaustively remove frequencies starting from the smallest counts to maximize the reduction in distinct types per removal cost k.

Intuition

The core insight relies on the Greedy Choice Property. We want to minimize the count of unique integers (distinct values), not just reduce the total array size. Removing an element with frequency 1 reduces our unique count immediately, whereas removing from a high-frequency number does not until that specific value is exhausted entirely. Since we have a fixed budget k, eliminating low-frequency groups first maximizes the reduction in unique types per unit cost of removals.

Approach

  1. Frequency Counting: Use a hash map (collections.Counter) to count occurrences of every integer in arr. This handles large values (10910^9) efficiently without array indexing issues, storing only O(M)O(M) entries where MM is the number of unique elements.
  2. Sort Frequencies: Extract just the frequency counts into a list and sort them in ascending order. We want to process numbers that appear least often first because they are “cheaper” to eliminate completely from our unique count perspective.
  3. Greedy Removal Simulation: Iterate through the sorted frequencies:
    • If k is greater than or equal to the current frequency, we can remove all instances of this number. Subtract its frequency from k, increment a counter for removed unique integers (or decrement total distinct count), and proceed.
    • If k is less than the current frequency, we cannot fully eliminate this integer type with our remaining budget. Since the list is sorted ascendingly, all subsequent frequencies will be greater or equal to the current one. Thus, no further unique integers can be completely removed. We stop here.
  4. Result Calculation: Return the total number of distinct elements minus those we successfully eliminated in step 3.

Complexity Analysis

  • Time Complexity: O(Nlog⁡N)O(N \log N) or more precisely O(Mlog⁡M+N)O(M \log M + N). Counting frequencies takes O(N)O(N) where NN is array length (10510^5). Sorting the unique counts (where MM is number of distinct elements, M≤NM \le N) takes O(Mlog⁡M)O(M \log M). Iterating through sorted list is O(M)O(M). In worst case (all unique), this becomes O(Nlog⁡N)O(N \log N), which fits well within time limits for FAANG interviews.
  • Space Complexity: O(N)O(N) or O(M)O(M) to store the frequency map and the sorted list of counts.

Solution

from collections import Counter
from typing import List

def findLeastNumOfUniqueInts(arr: List[int], k: int) -> int:
    # Count frequencies for each unique integer in arr
    freq_map = Counter(arr)
    
    # Extract just the frequency counts and sort them ascending.
    # We want to eliminate numbers with lowest occurrence first (greedy).
    sorted_freqs = sorted(freq_map.values())
    
    removed_unique_count = 0
    
    for count in sorted_freqs:
        if k >= count:
            # If we can remove all instances of this number, do so.
            k -= count
            removed_unique_count += 1
        else:
            # Cannot fully eliminate this number or any subsequent ones 
            # (since they have equal or higher frequency).
            break
            
    return len(sorted_freqs) - removed_unique_count

# Example usage matching problem description logic implicitly handled above.

Edge Cases Handled

  • k = 0: The loop condition if k >= count will fail immediately (unless counts are 0 which is impossible for existing elements), resulting in returning the total distinct count, which is correct as no removals occur.
  • All Elements Same (arr=[2,2,2]): Frequency list has one entry 3. If k >= 3, unique count becomes 0; else it remains 1. Logic holds.
  • k covers all elements: The loop completes successfully for every frequency in the sorted list. removed_unique_count equals total distinct, returning 0. Correct.
  • Empty Array (Constraint violation): Constraints state length ≥1\ge 1, but if it were empty, Counter returns empty dict, code would return 0 correctly.