Least Number of Unique Integers after K Removals

Given an array of integers arr and an integer k, find the least number of unique integers after removing exactly k elements from the array.

You may remove any k elements — they do not need to be contiguous.

Examples

Example 1:

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

Output: 1

Explanation: Remove one occurrence of 4, leaving [5, 5] which has 1 unique integer.

Example 2:

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

Output: 2

Explanation: Remove 4, 2, and one 1. The remaining array is [1, 3, 3, 3] which has 2 unique integers.

Example 3:

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

Output: 3

Explanation: Remove 2, 4, and 8 (each with frequency 1). The remaining array is [1, 3, 5, 1, 3] which has 3 unique integers.

Constraints

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^9
• 0 <= k <= arr.length