NeetCode #535LC-1481MediumHeap / Priority Queue
← Back to All Problems#535 · #1481 · Least Number of Unique Integers after K Removals(不同整数的最少数目)
📌 Problem Statement & Constraints
Given an integer array
arr and an integer k, remove exactly k elements so that the number of distinct remaining integers is minimised. Return that minimum. Constraints: 1 <= arr.length <= 10^5, 1 <= arr[i] <= 10^9, 0 <= k <= arr.length.💡 Core Algorithmic Approaches
- To minimise the number of distinct values, remove the elements belonging to the rarest values first.
- Count the frequencies, sort them ascending, and greedily remove entire groups while the budget allows.
- Each fully removed group reduces the distinct count by one.
- A partially removed group does not change the distinct count, so the loop stops as soon as a group does not fit.
💻 Benchmark Python3 Implementation
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
from collections import Counter
freqs = sorted(Counter(arr).values()) # rarest first
distinct = len(freqs)
for f in freqs:
if f > k:
break # cannot fully remove this group
k -= f
distinct -= 1
return distinct⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): the sort of the distinct frequencies dominates.
💾 Space Complexity
O(n) for the counter.
⚠️ Interview Pitfalls & Follow-ups
- Sorting the elements instead of the frequencies: the grouping is what matters.
- Removing partially from a group and decrementing the distinct count: a partial removal leaves the value present, so the count must not decrease.
- Stopping early with
breakinstead ofcontinue: the frequencies are sorted, so once one does not fit, no later one will --breakis correct. - Assuming
kmust be fully spent: unused removals are fine.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.