#1481

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Least Number of Unique Integers after K Removals

Find the least number of unique integers after removing exactly k elements from an array using efficient frequency counting and greedy strategy.

array hash table greedy sorting counting

Problem Statement

You are given an integer array arr and an integer k. Your task is to remove exactly k elements from the array and return the least number of unique integers left in the array after the removal.

For example, given arr = [5,5,4] and k = 1, removing the element 4 leaves only one unique number 5. You need to optimize the removal process based on frequency counting and consider a greedy approach to minimize the number of unique integers.

Examples

Example 1

Input: arr = [5,5,4], k = 1

Output: 1

Remove the single 4, only 5 is left.

Example 2

Input: arr = [4,3,1,1,3,3,2], k = 3

Output: 2

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 Approach

Count Frequencies

First, count the frequencies of all integers in the array using a hash map. This step allows you to know how many times each number appears, which is essential for the greedy approach.

Sort by Frequency

Sort the elements by their frequency. This helps prioritize removing the least frequent elements first, which will reduce the total number of unique integers left.

Greedy Removal of Elements

Start removing elements with the smallest frequencies until k removals are achieved. After removals, the remaining unique integers will be counted based on the untouched frequencies.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

The time complexity is O(n) because counting frequencies takes O(n), and sorting the frequencies takes O(n log n) in the worst case. However, the overall complexity is dominated by the frequency count, which makes the solution efficient. Space complexity is O(n) due to the storage of the frequency map.

What Interviewers Usually Probe

Candidate demonstrates proficiency in frequency counting and hash maps.
Approach effectively uses a greedy strategy to minimize the number of unique integers.
Candidate considers time complexity and implements an efficient solution.

Common Pitfalls or Variants

Common pitfalls

Not considering the greedy strategy of removing the least frequent elements first.
Incorrectly handling edge cases where k is 0 or the array has only one unique integer.
Failing to optimize the solution and resorting to unnecessary nested loops.

Follow-up variants

What if k is equal to the length of the array?
What if k is 0? How does the solution handle that?
How does the solution scale with a large input size, such as when arr.length approaches 100,000?

FAQ

What is the primary approach for solving the Least Number of Unique Integers after K Removals?

The primary approach involves counting the frequency of elements using a hash map, sorting them by frequency, and greedily removing the least frequent elements.

How does sorting by frequency help in the Least Number of Unique Integers after K Removals problem?

Sorting by frequency allows you to prioritize removing elements with the smallest counts first, minimizing the number of remaining unique integers.

What happens if k equals the length of the array?

If k equals the length of the array, all elements can be removed, leaving zero unique integers. The solution handles this case efficiently by iterating through all elements and removing them.

How do you optimize the solution for large arrays in the Least Number of Unique Integers after K Removals problem?

The solution is optimized by using hash maps to store frequencies, ensuring the complexity remains linear for counting, with the sorting operation being the only costly step (O(n log n)).

What is the worst-case time complexity of the Least Number of Unique Integers after K Removals?

The worst-case time complexity is O(n log n), where n is the length of the array, due to the sorting step. However, the overall process is efficient for large inputs.

terminal

Solution

Solution 1: 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$.

1

2

3

4

5

6

7

8

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        cnt = Counter(arr)
        for i, v in enumerate(sorted(cnt.values())):
            k -= v
            if k < 0:
                return len(cnt) - i
        return 0

Continue Practicing

#1090 largest values from labels #1054 distant barcodes #621 task scheduler