Least Number of Unique Integers after K Removals

Q: What is the time complexity of Least Number of Unique Integers after K Removals?

O(n log n). Counting frequencies takes O(n). Sorting the frequency list takes O(m log m), where m is the number of unique integers, which is at most n. The while loop iterates at most m times, so total complexity is dominated by sorting.

Q: What pattern does Least Number of Unique Integers after K Removals use?

The Pattern: Greedy Algorithms (Frequency-Based Removal) The Heuristic: When minimizing the count of unique elements after removals, always remove entire elements with the smallest frequencies first, as this yields the greatest reduction in unique count per removal cost.

Medium Greedy Algorithms

Problem

Given an integer array arr and an integer k, remove exactly k elements from the array such that the number of unique integers remaining is minimized, and return this minimum number of unique integers.

1 ≤ arr.length ≤ 10⁵
1 ≤ arr[i] ≤ 10⁹
1 ≤ k ≤ arr.length

Example

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

Output: 1

The frequency counts are {5: 2, 4: 1}. Removing one element from the integer with the smallest frequency (4) removes it entirely, leaving only one unique integer (5). This is the minimal number of unique integers achievable after removing k=1 elements.

Approach

Straightforward Solution

A brute-force approach would try all combinations of removing k elements, which is combinatorially explosive and infeasible for large arrays.

Core Observation

The minimal number of unique integers after removing k elements is achieved by removing entire integers with the smallest frequencies first, because removing all occurrences of a low-frequency integer reduces the unique count by one at the least cost.

Path to Optimal

Preview

The key insight is to count the frequencies of each integer, then sort these frequencies in ascending order. Removing integers with the smallest frequencies first uses the fewest removals to reduce the unique count…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Count frequencies using a hash map, sort the frequency values ascendingly, then greedily remove integers starting from the smallest frequency by subtracting their counts from k. Stop when k is less than the next frequency…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log n)

Counting frequencies takes O(n). Sorting the frequency list takes O(m log m), where m is the number of unique integers, which is at most n. The while loop iterates at most m times, so total complexity is dominated by sorting.

Space

O(n)

The frequency map stores counts for up to n unique integers in the worst case, requiring O(n) auxiliary space.

Pattern Spotlight

Greedy Algorithms (Frequency-Based Removal)

When minimizing the count of unique elements after removals, always remove entire elements with the smallest frequencies first, as this yields the greatest reduction in unique count per removal cost.

Solution

Python

1from collections import Counter
2
3class Solution:
  def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
      counts = Counter(arr)
      freqs = sorted(counts.values()) 
      
      i = 0
      while i < len(freqs) and k >= freqs[i]:
          k -= freqs[i]
          i += 1
      
      return len(freqs) - i

Step-by-Step Solution

Count Frequencies of Each Integer in the Array

5	`counts = Counter(arr)`

Objective

To build a frequency map that records how many times each integer appears in the array.

Key Insight

Knowing the frequency of each integer is essential because the cost to remove an integer entirely equals its frequency. This frequency map enables the greedy strategy to prioritize removals of integers with the smallest counts first.

Interview Quick-Check

Core Logic

Counting frequencies transforms the problem from element-level removals to frequency-level removals, enabling efficient greedy decisions.

Complexity

Frequency counting is O(n) time and O(n) space, where n is the array length.

Sort Frequencies to Prioritize Removal of Least Frequent Integers

To order the frequency counts in ascending order so that integers with the smallest frequencies can be removed first.

Greedily Remove Integers Starting from the Smallest Frequency

To iteratively subtract frequencies from k, removing entire integers until k is exhausted or no more integers can be fully removed.

Calculate and Return the Remaining Number of Unique Integers

To compute the final count of unique integers remaining after removals and return it.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 1 Critical line interviewers watch for.

Line 9 Critical

while i < len(freqs) and k >= freqs[i]:

Check if the current integer's frequency can be fully removed within the remaining k.

This conditional check is critical because removing an integer only reduces the unique count if all its occurrences are removed; partial removals do not reduce the unique count and would violate the problem constraints.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why does removing integers with the smallest frequencies first minimize the number of unique integers remaining?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Least Number of Unique Integers after K Removals from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Least Number of Unique Integers after K Removals drill

or drill a free problem

1	`from collections import Counter`
2
3	`class Solution:`
4	`def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:`
5	`counts = Counter(arr)`
6	`freqs = sorted(counts.values())`
7
8	`i = 0`
9	`while i < len(freqs) and k >= freqs[i]:`
10	`k -= freqs[i]`
11	`i += 1`
12
13	`return len(freqs) - i`