Skip to main content
Talentd

Least Number of Unique Integers after K Removals - Solution & Explanation

MediumArrayHash TableGreedySorting17 min readAsked at: Amazon, Morgan Stanley, Oracle +4
Practice this problem

Problem Statement

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

 

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
Example 2: 
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

Approach Overview

Problem Overview: You receive an integer array and an integer k. Remove exactly k elements so the number of distinct integers left in the array is as small as possible. The key observation: removing numbers that appear fewer times eliminates unique values faster than removing frequent numbers.

Approach 1: Frequency Count + Min-Heap (O(n + m log m) time, O(m) space)

Start by counting how many times each value appears using a hash map. This transforms the problem into managing frequencies instead of raw elements. Push all frequencies into a min-heap so the smallest counts come first. Repeatedly pop the smallest frequency and subtract it from k. If k is large enough to remove all occurrences of that number, you eliminate one unique integer. Continue until k is exhausted. The heap ensures you always remove the cheapest unique number first. Time complexity is O(n + m log m) where m is the number of distinct integers, and space complexity is O(m). This approach combines hash table counting with a priority queue for optimal removal order.

Approach 2: Greedy Frequency Counting with Sorting (O(n + m log m) time, O(m) space)

Instead of a heap, store the frequency counts in a list and sort them in ascending order. This produces the same removal order as the heap but uses sorting once instead of repeated heap operations. Iterate through the sorted frequencies. For each frequency f, check if k ≥ f. If true, remove all occurrences and reduce k by f, which eliminates one unique number. Once k becomes smaller than the next frequency, you stop because removing that number completely is impossible. The remaining count of frequencies gives the number of unique integers left. This greedy strategy works because removing smaller groups always yields the maximum reduction in unique values. Complexity is O(n + m log m) time and O(m) space due to the frequency map and sorting. This technique highlights classic greedy reasoning combined with sorting.

Recommended for interviews: The greedy frequency approach is what most interviewers expect. Building a frequency map and removing the smallest counts first demonstrates a clear understanding of greedy optimization. The min-heap solution shows stronger familiarity with priority queues and dynamic selection, while the sorted-frequency approach is simpler and often easier to implement quickly during interviews.

Approach 1: Approach with Frequency Count and Min-Heap

This approach involves two main steps. First, count the frequency of each integer in the array. Second, use a min-heap (or priority queue) to remove the integers with the smallest frequency first. This approach ensures that we are removing the least frequent integers to reach the least number of unique integers efficiently.

This C program implements the approach by utilizing an array to keep the frequency of each integer. It then collects these frequencies into another array which is sorted to allow removal of the lowest frequencies first. A loop continues removing these and reducing the count of unique integers. A direct index is maintained to access frequencies in order.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting the frequency array. Space Complexity: O(n) for storing the frequency counts.

Try this approach in the editor →

Approach 2: Greedy Approach with Frequency Counting

This approach takes a greedy strategy to count frequencies of integers and sorts them. By progressively removing elements with smallest frequencies, it directly calculates the least number of unique integers remaining after exactly k removals.

This implementation in C uses a frequency array to count each integer's occurrences. After sorting this array, elements are removed from the smallest frequency upwards until k removals are exhausted.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to the qsort on frequencies. Space Complexity: O(n) for arrays used in frequency counting.

Try this approach in the editor →

Approach 3: Hash Table + Sorting

We use the hash table cnt to count the number of times each integer in the array arr appears, and then sort the values in cnt in ascending order, and record them in the array nums.

Next, we traverse the array nums. For the current value that we traverse to nums[i], we subtract k by nums[i]. If k \lt 0, it means that we have removed k elements, and the minimum number of different integers in the array is the length of nums minus the index i that we traverse to at the current time. Return directly.

If we traverse to the end, it means that we have removed all the elements, and the minimum number of different integers in the array is 0.

The time complexity is O(n times log n), and the space complexity is O(n), where n is the length of the array arr.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach with Frequency Count and Min-Heap

Time Complexity: O(n log n) due to sorting the frequency array. Space Complexity: O(n) for storing the frequency counts.

Greedy Approach with Frequency Counting

Time Complexity: O(n log n) due to the qsort on frequencies. Space Complexity: O(n) for arrays used in frequency counting.

Hash Table + Sorting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Frequency Count + Min-HeapO(n + m log m)O(m)General case when you want dynamic access to the smallest frequency using a priority queue
Greedy Frequency Counting with SortingO(n + m log m)O(m)Simpler implementation when sorting frequencies once is acceptable

Video Solution

Least Number of Unique Integers after K Removal - Leetcode 1481 - Python • NeetCodeIO • 12,809 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Least Number of Unique Integers after K Removals easy or hard?
The problem is rated Medium because it requires recognizing a greedy strategy after converting the array into frequency counts. The implementation is straightforward once the key insight is clear, but identifying that removing the least frequent numbers first leads to the optimal result is the main challenge.
Least Number of Unique Integers after K Removals Python/Java solution
In Python, developers typically use collections.Counter to compute frequencies and heapq or sorting for the greedy step. Java implementations use HashMap for counting and PriorityQueue or Arrays.sort for ordering frequencies. Both approaches follow the same idea: remove the smallest frequency groups until k deletions are exhausted.
How to solve Least Number of Unique Integers after K Removals in O(n)?
A near O(n) solution can be achieved by counting frequencies and using a counting/bucket strategy instead of sorting or a heap. Group numbers by frequency and remove from the lowest frequency bucket first until k deletions are used. This avoids the log factor when the frequency range is limited, though most practical implementations use sorting or a min-heap.
What is the best approach for Least Number of Unique Integers after K Removals?
The optimal strategy uses greedy frequency removal. Count how many times each integer appears, then remove numbers with the smallest frequency first. This minimizes the number of deletions needed to eliminate a unique value. Implementations commonly use either a min-heap or a sorted list of frequencies, both running in O(n + m log m) time where m is the number of unique elements.
Is Least Number of Unique Integers after K Removals asked at Google/Amazon/Meta?
This pattern appears frequently in interviews at companies like Amazon, Google, and Meta because it tests frequency counting, greedy decision making, and efficient data structure usage. Candidates are expected to recognize that removing the least frequent numbers first minimizes the remaining unique elements.
What data structure is used in Least Number of Unique Integers after K Removals?
The solution relies on a hash map to count frequencies of elements. After counting, either a min-heap (priority queue) or a sorted array of frequencies is used to process the smallest counts first. These structures enable efficient greedy removal of elements.
What is the time complexity of Least Number of Unique Integers after K Removals?
The typical solution runs in O(n + m log m) time. O(n) is used to build the frequency map, and O(m log m) comes from either sorting the frequency list or maintaining a min-heap of size m. Space complexity is O(m) for storing the frequency counts of distinct integers.

Ready to solve this problem?

Practice Least Number of Unique Integers after K Removals with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Number of Distinct Elements After Operations