1481. Least Number of Unique Integers after K Removals

Problem Description

Given an array arr of integers and an integer k, the task is to determine the minimum number of unique integers that remain in the array after precisely k elements have been removed. The key to solving this problem lies in effectively selecting which elements to remove to achieve the least number of unique integers possible.

Intuition

To solve this problem, we should consider removing elements that appear more frequently first since this will not reduce the unique count as quickly. Ideally, we want to remove the numbers that occur the least amount of times last. We can apply a strategy that consists of the following steps:

1. Count the frequency of each unique integer in the array using a hash table (or Counter in Python).
2. Sort these unique integers by their frequency in ascending order. This way, the elements that appear less frequently are at the beginning of the sorted list.
3. Traverse the sorted list, and with each step, decrease k by the frequency of the current element. This simulates removing that element's occurrences from the array.
4. If k becomes negative, it means we can't remove all occurrences of the current element without exceeding the allowed k removals. Therefore, the current count of unique integers minus the number of elements we've been able to fully remove by this point gives us the answer.
5. If we go through the entire list without k becoming negative, it means we managed to remove all occurrences of certain elements, and we end up with 0 unique integers.

Having this strategy in place allows us to reach the solution in an efficient manner.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation of the solution follows a straightforward approach outlined in previous steps, which uses common data structures and algorithms:

1. Hash Table (Counter): We employ a hash table which is native to Python called Counter from the collections module. This structure automatically counts the frequency of each unique integer, which is essential to our strategy. It simplifies the process of determining how many times each integer appears in the array.

   1cnt = Counter(arr)

2. Sorting: After counting the occurrences of each integer, we sort these counts. This sorting is ascending, meaning that unique integers with fewer occurrences are considered first when we start removing elements.

   1sorted(cnt.values())

3. Traversal and Subtraction: With the sorted frequencies, we traverse the list. For each frequency value v, we subtract k by v, simulating the removal of v occurrences from the array.

   1for i, v in enumerate(sorted(cnt.values())):
   2    k -= v
   3    ...

   • If k becomes less than zero during the iteration, it indicates that we cannot remove all occurrences of the current element as it would exceed k. Hence, the minimal number of unique integers is obtained by subtracting the current index i from the total number of unique integers (the length of cnt):

     1if k < 0:
     2    return len(cnt) - i

4. Return Result: If we are able to traverse the entire sorted list of frequencies without k becoming negative, we have managed to remove all occurrences of certain elements leading to zero unique integers left.

   1return 0

The overall complexity of the solution is determined mainly by the sorting operation and the counting operation, with the rest being linear traversals and basic arithmetic operations.

Example Walkthrough

Let's use a small example to illustrate the solution approach:

Suppose arr = [4, 3, 1, 1, 2, 3, 3] and k = 3. Our goal is to remove k elements from arr in such a way that the number of unique integers remaining is minimal.

1. Count Frequency: We first count how many times each integer appears in the array:

   • 1 appears 2 times
   • 2 appears 1 time
   • 3 appears 3 times
   • 4 appears 1 time

   Using a hash table:

   cnt = {1: 2, 2: 1, 3: 3, 4: 1}

2. Sort by Frequency: We sort these counts in ascending order based on frequency:

   Sorted counts: [1, 1, 2, 3]

   The number of unique integers is initially 4.

3. Traverse and Remove: We then traverse the sorted list and remove k elements.

   • We start with the first element (frequency of 1). We remove one instance of the integer with a count of 1, which decreases k to 2.
   • We move to the next element (another frequency of 1). We remove one instance of another integer with a count of 1, which decreases k to 1.
   • With the third element (frequency of 2), we can remove both instances of the integer 1, which would decrease k to -1.

   However, since we can't go negative, it means we can't remove all instances of 1. At this point, we have removed two unique integers (those with the initial frequency of 1), resulting in a remaining unique integer count of 2 (those with frequencies of 2 and 3 are still present).

   Here's the traversal in action:

   1cnt = {1: 2, 2: 1, 3: 3, 4: 1}
   2sorted_counts = [1, 1, 2, 3]
   3k = 3
   4for i, v in enumerate(sorted_counts):
   5    k -= v
   6    if k < 0:
   7        return 4 - i  # number of unique integers initially minus the index

4. Return Result: With the loop broken, we know we've removed instances of unique integers only until the array's k becomes negative. This means we return 4 - 2, which equals 2.

Therefore, the minimum number of unique integers remaining in the array arr after removing exactly k elements is 2.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(n log n). This complexity arises from the sorting operation sorted(cnt.values()) where cnt.values() represents the counts of unique integers in the array arr; sorting these counts requires O(n log n) time since sorting is typically done using comparison-based algorithms like quicksort or mergesort which have O(n log n) complexity in the average and worst case.

The space complexity of the code is O(n) because we are storing counts of the elements in the array in a dictionary cnt. In the worst case, if all elements are unique, it will contain n key-value pairs which relate directly to the size of the input array arr.

Learn more about how to find time and space complexity quickly using problem constraints.