Leetcode 1481: Least Number of Unique Integers after K Removals
You are given an array of integers arr and an integer k. You need to remove exactly k elements from the array and find the minimum number of unique integers that remain in the array.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of integers arr and an integer k.
Example: [10, 10, 20], k = 1
Constraints:
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length
Output: The output should be a single integer representing the minimum number of unique integers remaining after removing exactly k elements.
Example: 1
Constraints:
• The result is guaranteed to be a valid integer.
Goal: The goal is to remove exactly k elements while minimizing the number of unique integers left in the array.
Steps:
• Count the frequency of each element in the array.
• Sort the elements by their frequency in ascending order.
• Remove elements starting from the least frequent until exactly k elements are removed.
• Return the number of unique elements remaining.
Goal: The constraints ensure that the input size is large enough to require an efficient approach to minimize the number of unique integers left.
Steps:
• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length
Assumptions:
• The array can contain duplicate elements.
• The value of k can be zero, meaning no elements need to be removed.
• Input: [10, 10, 20], k = 1
• Explanation: Here, the optimal approach is to remove the single `20`, leaving only `10` as the remaining unique integer.
Approach: To solve this problem, count the frequency of each element, sort the elements based on frequency, and remove the least frequent elements first to minimize the number of unique integers remaining.
Observations:
• The problem requires reducing the number of unique elements after removal, so we should focus on removing the least frequent elements.
• By sorting the elements based on their frequencies, we can efficiently determine which elements to remove.
Steps:
• Count the frequency of each element in the array using a hash map.
• Sort the elements by their frequency in ascending order.
• Remove elements starting with the least frequent until exactly k elements are removed.
• Return the number of unique elements left after the removal process.
Empty Inputs:
• If the array is empty, return 0 since no elements are left.
Large Inputs:
• Ensure the solution handles arrays with up to 10^5 elements efficiently.
Special Values:
• If k is 0, no elements are removed, and the number of unique elements should be returned as is.
Constraints:
• The algorithm must be efficient enough to handle the upper limit of input size.
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
unordered_map<int, int> mp;
for(auto m : arr) mp[m]++;
sort(begin(arr), end(arr), [&](int x, int y) {
return mp[x] != mp[y] ? mp[x] < mp[y] : x < y;
});
unordered_set<int> st;
for(int i = k; i < arr.size(); i++) st.insert(arr[i]);
return st.size();
}
1 : Method
int findLeastNumOfUniqueInts(vector<int>& arr, int k) {
This is the function signature for `findLeastNumOfUniqueInts`, which takes an array `arr` and an integer `k` as inputs and returns the number of unique integers left after removing `k` elements.
2 : Data Structure
unordered_map<int, int> mp;
An unordered map `mp` is created to store the frequency of each integer in the array `arr`.
3 : Loop
for(auto m : arr) mp[m]++;
This loop iterates through each element in the array `arr` and increments its frequency in the unordered map `mp`.
4 : Sorting Logic
sort(begin(arr), end(arr), [&](int x, int y) {
The `sort` function sorts the elements in `arr` using a custom comparator. It compares the frequency of the integers from the map `mp`.
5 : Comparison
return mp[x] != mp[y] ? mp[x] < mp[y] : x < y;
The comparator sorts first by frequency (`mp[x] < mp[y]`), and if the frequencies are equal, it sorts by the integer value itself (`x < y`).
6 : Loop
unordered_set<int> st;
An unordered set `st` is used to store the unique integers remaining after removing `k` elements from the array.
7 : Removal
for(int i = k; i < arr.size(); i++) st.insert(arr[i]);
Starting from index `k`, the remaining elements are inserted into the unordered set `st`, effectively removing the first `k` elements.
8 : Return
return st.size();
The function returns the size of the set `st`, which is the count of unique integers left in the array after removal.
Best Case: O(n log n) for sorting the elements based on frequency.
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting step, which is O(n log n), where n is the length of the array.
Best Case: O(n)
Worst Case: O(n) for storing the frequency map and the sorted list of elements.
Description: The space complexity is O(n) due to the storage required for the frequency map and the sorted elements.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus