Least Number of Unique Integers after K Removals solution and explanation
Google
9 more videos on this problem
Least Number of Unique Integers after K Removal - Leetcode 1481 - PythonNeetCodeIO · 18:27 · 12K views
Least Number of Unique Integers after K Removals | 3 Approaches | Greedy | Leetcode 1481codestorywithMIK · 43:42 · 5K views
1481. Least Number of Unique Integers after K Removals (python) (Leetcode Medium)Programming Live with Larry · 5:24 · 3K views
Least Number of Unique Integers after K Removals (Leetcode 1481)Coding Interviews · 10:34 · 2K views
Leetcode Question 1481: Least Number of Unique Integers after K RemovalsFMVP · 7:55 · 577 views
Leet Code 1481 Least Number of Unique Integers after K RemovalsTechConfab · 12:54 · 484 views
HOW TO FIND Least Number of Unique Integers after K Removals - Leetcode 1481 - PythonLit Code · 7:22 · 134 views
Leetcode 1481: Least Number of Unique Integers after K RemovalsAlgorithms Casts · 12:15 · 83 views
LeetCode 1481 - Least Number of Unique Integers after K Removals - PythonAlpha-Code · 9:12 · 77 views
1481. Least Number of Unique Integers after K Removals || Solved using min Heap 🔥 || C++Priyanshi Porwal · 18:37 · 68 views
The problem
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^51 <= arr[i] <= 10^90 <= 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.
from collections import Counter
def least_number_of_unique_ints(arr, k):
freq = Counter(arr)
frequencies = sorted(freq.values())
unique_count = len(frequencies)
for f in frequencies:
if k >= f:
k -= f
unique_count -= 1
else:
break
return unique_count
arr = [4, 3, 1, 1, 3, 3, 2]
k = 3
print(least_number_of_unique_ints(arr, k))import java.util.*;
public class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
Map<Integer, Integer> frequencyMap = new HashMap<>();
for (int num : arr) {
frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
}
List<Integer> frequencyList = new ArrayList<>(frequencyMap.values());
Collections.sort(frequencyList);
int uniqueCount = frequencyList.size();
for (int freq : frequencyList) {
if (k >= freq) {
k -= freq;
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] arr = {4, 3, 1, 1, 3, 3, 2};
int k = 3;
System.out.println(solution.findLeastNumOfUniqueInts(arr, k));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int leastNumberOfUniqueInts(vector<int>& arr, int k) {
unordered_map<int, int> freqMap;
for (int num : arr) {
freqMap[num]++;
}
vector<int> freqValues;
for (auto entry : freqMap) {
freqValues.push_back(entry.second);
}
sort(freqValues.begin(), freqValues.end());
int uniqueCount = freqValues.size();
for (int freq : freqValues) {
if (k >= freq) {
k -= freq;
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
int main() {
vector<int> arr = {4, 3, 1, 1, 3, 3, 2};
int k = 3;
cout << leastNumberOfUniqueInts(arr, k) << endl;
return 0;
}function leastNumberOfUniqueInts(arr, k) {
const freqMap = new Map();
for (let num of arr) {
freqMap.set(num, (freqMap.get(num) || 0) + 1);
}
let frequencies = Array.from(freqMap.values());
frequencies.sort((a, b) => a - b);
let uniqueCount = frequencies.length;
for (let freq of frequencies) {
if (k >= freq) {
k -= freq;
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
const arr = [4, 3, 1, 1, 3, 3, 2];
const k = 3;
console.log(leastNumberOfUniqueInts(arr, k));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
int leastNumberOfUniqueInts(int* arr, int arrSize, int k) {
int frequency[100001] = {0};
for (int i = 0; i < arrSize; ++i) {
frequency[arr[i]]++;
}
int frequencies[100001] = {0};
int index = 0;
for (int i = 0; i < 100001; ++i) {
if (frequency[i] > 0) {
frequencies[index++] = frequency[i];
}
}
qsort(frequencies, index, sizeof(int), compare);
int uniqueCount = index;
for (int i = 0; i < index && k > 0; ++i) {
if (frequencies[i] <= k) {
k -= frequencies[i];
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
int main() {
int arr[] = {4, 3, 1, 1, 3, 3, 2};
int k = 3;
printf("%d\n", leastNumberOfUniqueInts(arr, sizeof(arr) / sizeof(arr[0]), k));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
class Solution {
public int LeastNumberOfUniqueInts(int[] arr, int k) {
var freqMap = new Dictionary<int, int>();
foreach (var num in arr) {
if (freqMap.ContainsKey(num))
freqMap[num]++;
else
freqMap[num] = 1;
}
var frequencies = freqMap.Values.ToList();
frequencies.Sort();
int uniqueCount = frequencies.Count;
foreach (var freq in frequencies) {
if (k >= freq) {
k -= freq;
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
static void Main(string[] args) {
int[] arr = {4, 3, 1, 1, 3, 3, 2};
int k = 3;
Solution s = new Solution();
Console.WriteLine(s.LeastNumberOfUniqueInts(arr, k));
}
}The Python solution uses the Counter from the collections module to count frequencies. The frequencies are then sorted to facilitate selective removal, maintaining a count of unique items efficiently.
Time Complexity: O(n log n) due to sorting the frequency values. Space Complexity: O(n) for the frequency Counter storage.
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.
def least_number_of_unique_ints(arr, k):
from collections import Counter
count = Counter(arr)
frequencies = sorted(count.values())
unique = len(frequencies)
for f in frequencies:
if k >= f:
k -= f
unique -= 1
else:
break
return unique
arr = [5, 5, 4]
k = 1
print(least_number_of_unique_ints(arr, k))import java.util.*;
public class Solution {
public int findLeastNumOfUniqueInts(int[] arr, int k) {
HashMap<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
List<Integer> frequencies = new ArrayList<>(freq.values());
Collections.sort(frequencies);
int uniqueCount = frequencies.size();
for (int f : frequencies) {
if (k >= f) {
k -= f;
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {5, 5, 4};
System.out.println(sol.findLeastNumOfUniqueInts(arr, 1));
}
}#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int leastNumberOfUniqueInts(vector<int>& arr, int k) {
unordered_map<int, int> count;
for (int num : arr) {
count[num]++;
}
vector<int> frequencies;
for (auto& kvp : count) {
frequencies.push_back(kvp.second);
}
sort(frequencies.begin(), frequencies.end());
int unique = frequencies.size();
for (int freq : frequencies) {
if (k >= freq) {
k -= freq;
unique--;
} else {
break;
}
}
return unique;
}
int main() {
vector<int> arr = {5, 5, 4};
int k = 1;
cout << leastNumberOfUniqueInts(arr, k) << endl;
return 0;
}function leastNumberOfUniqueInts(arr, k) {
const frequencyMap = new Map();
for (const num of arr) {
frequencyMap.set(num, frequencyMap.has(num) ? frequencyMap.get(num) + 1 : 1);
}
const frequencies = Array.from(frequencyMap.values()).sort((a, b) => a - b);
let unique = frequencies.length;
for (const freq of frequencies) {
if (k >= freq) {
k -= freq;
unique--;
} else {
break;
}
}
return unique;
}
console.log(leastNumberOfUniqueInts([5, 5, 4], 1));#include <stdio.h>
#include <stdlib.h>
int compare(const void* a, const void* b) {
return (*(int*)a) - (*(int*)b);
}
int leastNumberOfUniqueInts(int* arr, int arrSize, int k) {
int frequency[100001] = {0};
for (int i = 0; i < arrSize; i++) {
frequency[arr[i]]++;
}
int frequencies[100001];
int count = 0;
for (int i = 0; i < 100001; i++) {
if (frequency[i]) frequencies[count++] = frequency[i];
}
qsort(frequencies, count, sizeof(int), compare);
int uniqueCount = count;
for (int i = 0; i < count; i++) {
if (k >= frequencies[i]) {
k -= frequencies[i];
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
int main() {
int arr[] = {5, 5, 4};
int k = 1;
printf("%d\n", leastNumberOfUniqueInts(arr, sizeof(arr)/sizeof(arr[0]), k));
return 0;
}using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
public int LeastNumberOfUniqueInts(int[] arr, int k) {
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (int num in arr) {
if (count.ContainsKey(num))
count[num]++;
else
count[num] = 1;
}
List<int> frequencies = count.Values.ToList();
frequencies.Sort();
int uniqueCount = frequencies.Count;
foreach (int f in frequencies) {
if (k >= f) {
k -= f;
uniqueCount--;
} else {
break;
}
}
return uniqueCount;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.LeastNumberOfUniqueInts(new int[] {5, 5, 4}, 1));
}
}The Python solution uses the Counter class for efficient frequency counting, then sorts frequencies to optimize deletions. This minimizes unique integer count post k removals.
Time Complexity: O(n log n) owing to sorting frequency array. Space Complexity: O(n) for holding frequency counts.
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.
function findLeastNumOfUniqueInts(arr: number[], k: number): number {
const cnt: Map<number, number> = new Map();
for (const x of arr) {
cnt.set(x, (cnt.get(x) ?? 0) + 1);
}
const nums = [...cnt.values()].sort((a, b) => a - b);
for (let i = 0; i < nums.length; ++i) {
k -= nums[i];
if (k < 0) {
return nums.length - i;
}
}
return 0;
}func findLeastNumOfUniqueInts(arr []int, k int) int {
cnt := map[int]int{}
for _, x := range arr {
cnt[x]++
}
nums := make([]int, 0, len(cnt))
for _, v := range cnt {
nums = append(nums, v)
}
sort.Ints(nums)
for i, v := range nums {
k -= v
if k < 0 {
return len(nums) - i
}
}
return 0
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach with Frequency Count and Min-Heap | Time Complexity: O(n log n) due to sorting the frequency values. Space Complexity: O(n) for the frequency Counter storage. |
| Greedy Approach with Frequency Counting | Time Complexity: O(n log n) owing to sorting frequency array. Space Complexity: O(n) for holding frequency counts. |
| Hash Table + Sorting | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Frequency Count + Min-Heap | O(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 Sorting | O(n + m log m) | O(m) | Simpler implementation when sorting frequencies once is acceptable |
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.