Least Number of Unique Integers after K Removals

Medium
104.

Least Number of Unique Integers after K Removals

Least Number of Unique Integers after K Removals is a medium coding problem on arrays, hash table and greedy.

Given an integer array arr and an integer k, remove exactly k elements so that the number of distinct values remaining is as small as possible, and return that count.

Example 1

Input
arr = [5,5,4], k = 1
Output
1
Explanation
Remove the 4; only 5 remains.

Example 2

Input
arr = [4,3,1,1,3,3,2], k = 3
Output
2
Explanation
Remove 4, 2 and one 1.

Constraints

  • 1 <= arr.length <= 30
  • 1 <= arr[i] <= 50
  • 0 <= k <= arr.length
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findLeastNumOfUniqueInts = function(arr, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Least Number of Unique Integers after K Removals — Solution

Least Number of Unique Integers after K Removals solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Least Number of Unique Integers after K Removals is a medium coding problem on arrays, hash table and greedy.

  • Difficulty: Medium
  • Topics: Arrays, Hash Table, Greedy, Heap
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an integer array arr and an integer k, remove exactly k elements so that the number of distinct values remaining is as small as possible, and return that count.

Example 1

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the 4; only 5 remains.

Example 2

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and one 1.

Constraints

  • 1 <= arr.length <= 30
  • 1 <= arr[i] <= 50
  • 0 <= k <= arr.length

Hints for Least Number of Unique Integers after K Removals

  1. Hint 1

    Eliminate the rarest values first — they cost the fewest removals.

  2. Hint 2

    Sort the frequency counts ascending and consume k greedily.

How to solve Least Number of Unique Integers after K Removals

Removing a value entirely costs exactly as many deletions as its frequency, and removing only some copies of a value buys you nothing — the value still counts as distinct. So the whole problem is: with a budget of k, eliminate as many values as possible, and the cheapest values to eliminate are the rarest ones.

Approach

  1. Count how many times each value occurs.
  2. Collect the frequencies and sort them ascending.
  3. Walk them from smallest to largest, spending k on each frequency you can afford in full and decrementing the count of distinct values.
  4. Stop at the first frequency you cannot pay for — everything after it is at least as expensive.
  5. Return the number of distinct values still standing.

Why it works

This is a classic exchange argument. Take any optimal solution that eliminates a set of values; if it skips a cheaper value in favour of a dearer one, swapping them keeps the same number of values eliminated and frees budget, so it is no worse. Repeating the swap turns any optimum into the greedy "cheapest first" order — so greedy is optimal. Partial removals are provably wasted, because spending on copies without finishing a value does not reduce the distinct count.

Complexity

  • Time — O(n + d log d)
  • Space — O(d)

Pitfalls

  • You must be able to afford a frequency in full before eliminating it; a partial spend does not reduce the answer and just wastes budget.
  • Sort the frequencies ascending, not the values.
  • k may be 0, and it may be large enough to remove everything — both must fall out of the loop naturally.
  • Break out of the loop at the first unaffordable frequency; continuing to scan can wrongly skip past it to a coincidentally cheaper one (there isn't one once sorted, but the logic must not rely on that).

Reference solution

Python

from typing import List
from collections import Counter

def findLeastNumOfUniqueInts(arr: List[int], k: int) -> int:
    freqs = sorted(Counter(arr).values())
    remaining = len(freqs)
    for f in freqs:
        if k >= f:
            k -= f
            remaining -= 1
        else:
            break
    return remaining

Java

public static int findLeastNumOfUniqueInts(int[] arr, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
    List<Integer> freqs = new ArrayList<>(count.values());
    Collections.sort(freqs);
    int remaining = freqs.size();
    int budget = k;
    for (int f : freqs) {
        if (budget >= f) {
            budget -= f;
            remaining--;
        } else {
            break;
        }
    }
    return remaining;
}

C++

int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
    map<int, int> count;
    for (int x : arr) count[x]++;
    vector<int> freqs;
    for (const auto& e : count) freqs.push_back(e.second);
    sort(freqs.begin(), freqs.end());
    int remaining = (int) freqs.size();
    int budget = k;
    for (int f : freqs) {
        if (budget >= f) {
            budget -= f;
            remaining--;
        } else {
            break;
        }
    }
    return remaining;
}

JavaScript

var findLeastNumOfUniqueInts = function(arr, k) {
    const count = new Map();
    for (const x of arr) count.set(x, (count.get(x) || 0) + 1);
    const freqs = Array.from(count.values()).sort(function(a, b) { return a - b; });
    let remaining = freqs.length;
    for (const f of freqs) {
        if (k >= f) {
            k -= f;
            remaining--;
        } else {
            break;
        }
    }
    return remaining;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets