Problem

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

Examples

Example 1

1
2
3

Input: arr = [5,5,4], k = 1
Output: 1
**Explanation** : Remove the single 4, only 5 is left.

Example 2

1
2
3

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
**Explanation** : Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • 0 <= k <= arr.length

Solution

Method 1 – Greedy with Frequency Counting

Intuition

To minimize the number of unique integers after removing exactly k elements, we should remove the integers with the lowest frequencies first. This way, we can eliminate more unique numbers with fewer removals.

Approach

  1. Count the frequency of each integer in arr.
  2. Sort the frequencies in ascending order.
  3. Iterate through the sorted frequencies, subtracting from k for each frequency removed.
  4. Stop when k is less than the next frequency; the answer is the number of unique integers left.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
        unordered_map<int, int> freq;
        for (int x : arr) freq[x]++;
        vector<int> counts;
        for (auto& p : freq) counts.push_back(p.second);
        sort(counts.begin(), counts.end());
        int ans = counts.size();
        for (int c : counts) {
            if (k >= c) { k -= c; ans--; }
            else break;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

func findLeastNumOfUniqueInts(arr []int, k int) int {
    freq := map[int]int{}
    for _, x := range arr { freq[x]++ }
    counts := []int{}
    for _, v := range freq { counts = append(counts, v) }
    sort.Ints(counts)
    ans := len(counts)
    for _, c := range counts {
        if k >= c { k -= c; ans-- } else { break }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : arr) freq.put(x, freq.getOrDefault(x, 0) + 1);
        List<Integer> counts = new ArrayList<>(freq.values());
        Collections.sort(counts);
        int ans = counts.size();
        for (int c : counts) {
            if (k >= c) { k -= c; ans--; }
            else break;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun findLeastNumOfUniqueInts(arr: IntArray, k: Int): Int {
        val freq = arr.groupingBy { it }.eachCount()
        val counts = freq.values.sorted()
        var ans = counts.size
        var rem = k
        for (c in counts) {
            if (rem >= c) { rem -= c; ans-- } else break
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def findLeastNumOfUniqueInts(self, arr: list[int], k: int) -> int:
        from collections import Counter
        freq = Counter(arr)
        counts = sorted(freq.values())
        ans = len(counts)
        for c in counts:
            if k >= c:
                k -= c
                ans -= 1
            else:
                break
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

impl Solution {
    pub fn find_least_num_of_unique_ints(arr: Vec<i32>, k: i32) -> i32 {
        use std::collections::HashMap;
        let mut freq = HashMap::new();
        for x in arr { *freq.entry(x).or_insert(0) += 1; }
        let mut counts: Vec<_> = freq.values().cloned().collect();
        counts.sort();
        let mut ans = counts.len() as i32;
        let mut k = k;
        for c in counts {
            if k >= c { k -= c; ans -= 1; } else { break; }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    findLeastNumOfUniqueInts(arr: number[], k: number): number {
        const freq = new Map<number, number>();
        for (const x of arr) freq.set(x, (freq.get(x) ?? 0) + 1);
        const counts = Array.from(freq.values()).sort((a, b) => a - b);
        let ans = counts.length;
        for (const c of counts) {
            if (k >= c) { k -= c; ans--; } else break;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of arr (for sorting the frequencies).
  • 🧺 Space complexity: O(n), for the frequency map and counts array.