1481. Least Number of Unique Integers after K Removals

Understanding the Problem:

Before we dive into the code, let’s take a moment to understand the problem at hand. We’re given an array of integers and a value k, representing the maximum number of elements we can remove from the array. Our goal is to determine the least number of unique integers remaining in the array after removing k elements.

The Solution Approach:

To solve this problem, our Java solution employs a clever combination of data structures, including HashMaps and ArrayLists, along with sorting and iteration. Let’s break down the key components of the code:

class Frequency implements Comparable<Frequency> {
    int number, freq;
    Frequency (int s, int e) {
        number = s;
        freq = e;

    public int compareTo(Frequency other) {
        return Integer.compare(this.freq, other.freq);
class Solution {
    public int findLeastNumOfUniqueInts(int[] arr, int k) {
        HashMap<Integer, Frequency> map = new HashMap<Integer, Frequency>();
        for(int i=0;i<arr.length;i++) {
            if (map.containsKey(arr[i])) {
            } else {
                map.put(arr[i], new Frequency(arr[i], 1));
        ArrayList<Frequency> freq = new ArrayList<Frequency>();
        for (Map.Entry<Integer,Frequency> mapElement : map.entrySet()) {
        for(int i=0;i<freq.size();i++) {
            if (k == 0) {
               return freq.size() - i; 
            } else if (k < 0) {
                return freq.size() - i + 1;
            k -= freq.get(i).freq;
        if (k == 0) {
            return 0; 
        return 1;
  1. Frequency Class: We start by defining a Frequency class that represents each integer in the array along with its frequency (i.e., the number of times it appears in the array). This class implements the Comparable interface to enable sorting based on frequency.
  2. Solution Class: The main solution logic resides in the findLeastNumOfUniqueInts method of the Solution class. Here’s a step-by-step breakdown:
    • We initialize a HashMap to store each integer along with its frequency.
    • We iterate through the array and update the frequency count in the HashMap.
    • We then transfer the frequency entries from the HashMap to an ArrayList for sorting.
    • Next, we sort the ArrayList of Frequency objects based on frequency in ascending order.
    • Finally, we iterate through the sorted list, decrementing k by the frequency of each element. We return the count of unique integers when k becomes zero or negative.

Conclusion: Through the power of Java programming and algorithmic thinking, we’ve successfully tackled the challenge of finding the least number of unique integers after removing k elements from an array. By leveraging data structures, sorting techniques, and iterative algorithms, we’ve crafted a robust and efficient solution to this intriguing puzzle. So the next time you encounter a coding challenge, remember to break it down into smaller components, analyze the problem requirements, and unleash the full potential of your coding skills. Happy coding!

Related Post