⚡Flashcard Drill➔
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

  1. To minimise the number of distinct values, remove the elements belonging to the rarest values first.
  2. Count the frequencies, sort them ascending, and greedily remove entire groups while the budget allows.
  3. Each fully removed group reduces the distinct count by one.
  4. 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 break instead of continue: the frequencies are sorted, so once one does not fit, no later one will -- break is correct.
  • Assuming k must 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.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems