We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Least Number of Unique Integers after K Removals

Difficulty: Medium

Problem Description

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

Key Insights

  • The goal is to minimize the number of unique integers in the array after removing k elements.
  • Removing elements with higher frequency first will likely lead to a greater reduction in unique integers.
  • A count of each integer's occurrences can help prioritize which integers to remove.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the frequency counts. Space Complexity: O(n) - for storing the frequency counts and unique integers.

Solution

To solve this problem, we will use the following approach:

  1. Count the frequency of each integer in the array using a hash table (or dictionary).
  2. Store these frequencies in a list and sort them in ascending order.
  3. Iterate through the sorted frequencies, removing elements starting from the least frequent until we've removed exactly k elements.
  4. Count how many unique integers remain after the removals.

This approach effectively prioritizes the removal of the least frequent integers, ensuring that we minimize the number of unique integers left in the array.

Code Solutions

from collections import Counter

def findLeastNumOfUniqueInts(arr, k):
    # Count the frequency of each integer
    freq = Counter(arr)
    
    # Retrieve the frequencies and sort them
    counts = sorted(freq.values())
    
    # Remove elements starting from the least frequent
    unique_count = len(counts)
    for count in counts:
        if k >= count:
            k -= count
            unique_count -= 1
        else:
            break
    
    return unique_count
← Back to All Questions