Practice/Google/Leetcode 1481. Least Number of Unique Integers after K Removals

Leetcode 1481. Least Number of Unique Integers after K Removals

CodingMust

Problem

Given an array of integers and a positive integer k, you must remove exactly k elements from the array. Your goal is to minimize the count of distinct integers that remain in the array after these removals.

Return the minimum number of distinct integers that can remain after removing exactly k elements.

Requirements

1. Remove exactly k elements from the input array
2. Minimize the number of distinct integer values in the resulting array
3. Return the count of distinct integers remaining after optimal removals
4. Elements can be removed in any order

Constraints

• 1 ≤ arr.length ≤ 10⁵
• 1 ≤ arr[i] ≤ 10⁹
• 0 ≤ k ≤ arr.length
• Time complexity should be O(n log n) or better where n is the array length
• Space complexity should be O(n) or better

Examples

Example 1:

Input: arr = [5, 5, 4], k = 1 Output: 1 Explanation: Remove the element 4 (which appears once). Now only the value 5 remains, giving us 1 distinct value.

Example 2:

Input: arr = [4, 3, 1, 1, 3, 3, 2], k = 3 Output: 2 Explanation: Remove 4 (appears 1 time), 2 (appears 1 time), and one occurrence of 1 (appears 2 times). We've eliminated 2 complete distinct values (4 and 2), leaving 2 distinct values (1 and 3).

Example 3:

Input: arr = [1, 1, 1, 1], k = 2 Output: 1 Explanation: We can only remove 2 out of the 4 ones. The value 1 still remains, so 1 distinct value remains.