Least Number of Unique Integers after K Removals

Patrick Leaton
Published: Sept. 23, 2021, 6:19 p.m.
Problem Description

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

 

 

The description was taken from https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/.

Problem Solution

#O(N(Log(N))) Time, O(N) Space
class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        seen, heap = {}, []
        removals = 0
       
        for num in arr:
            if num not in seen:
                seen[num] = 1
            else:
                seen[num] += 1
                       
        for num in seen:
            heapq.heappush(heap, (seen[num], num))
       
        while removals < k:
            frequency, num = heapq.heappop(heap)
            frequency -= 1
            removals += 1
            if frequency > 0:
                heapq.heappush(heap, (frequency, num))
       
        return len(heap)

Problem Explanation

This is a greedy problem.

One of the clues is when the description wants us to return the minimum or least amount of iterations to accomplish something.  Typically when k is in the problem description as well, that it is an indication that a heap may be used also.

What we will do is group each character by frequency, then push those groups into a heap and continuously remove the least frequent character until we have done this k times.

We are wanting to end up with the least amount of unique integers at the end, so that is why we remove the least frequent characters first because those will give us the best chance to get rid of the most unique characters.  If we wanted to end up with the greatest amount, we would instead remove the most frequent characters.

Let's start by initializing our integer frequency hashmap, and our heap.

        seen, heap = {}, []

 

We will also want to keep track of our removals so that we know when we have removed enough elements.

        removals = 0

 

For each number in the array, if we haven't seen the number yet then we will store it in our hashmap with an initial frequency of one.  Otherwise, we will increment this integer's frequency value.

        for num in arr:
            if num not in seen:
                seen[num] = 1
            else:
                seen[num] += 1

 

Now that we have the frequencies of each integer, we will push the frequency and the integer into the heap.  The integer doesn't need to really go in at this point because we really just care about the frequency of unique characters, but this is helpful for testing.

        for num in seen:
            heapq.heappush(heap, (seen[num], num))

 

Now, while we have removed less than k elements from the heap, we will continue to pop the least frequent number off of the heap, remove one of its elements, and if the count of this number is greater than zero, we will push it back in.

        while removals < k:
            frequency, num = heapq.heappop(heap)
            frequency -= 1
            removals += 1
            if frequency > 0:
                heapq.heappush(heap, (frequency, num))

 

Once we have finished removing k elements, we will return the length of the heap because each index in the heap is a unique character and its frequency count.

        return len(heap)