Teaching Kids Programming – Least Number of Unique Integers after K Removals

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

Least Number of Unique Integers after K Removals

Intuitively, we want to remove the numbers that appear less. In order to do this, we need to count the frequencies for the elements, we can use the Counter a.k.a hash map to count. Then, we need to be able to iterate the elements in the ascending order of their occurence frequency. Ideally, we can use the Counter‘s least_common method. However, it doesn’t have this method, but we can get the most_common() and then reverse it.

We then greedily remove the elements that appear less, until we cannot. The time/space complexity is O(N) where N is the number of the elements in the array.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        ans = len(c)
        for _, v in c.most_common()[::-1]:
            if k >= v:
                k -= v
                ans -= 1
            else:
                break
        return ans

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        c = Counter(arr)
        ans = len(c)
        for _, v in c.most_common()[::-1]:
            if k >= v:
                k -= v
                ans -= 1
            else:
                break
        return ans

–EOF (The Ultimate Computing & Technology Blog) —