1481. Least Number of Unique Integers after K Removals

Problem

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&nbsp;<= 10^5

• 1 <= arr[i] <= 10^9

• 0 <= k&nbsp;<= arr.length

Solution 1

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findLeastNumOfUniqueInts = function(arr, k) {
    var map = {};
    for (var i = 0; i < arr.length; i++) {
        map[arr[i]] = (map[arr[i]] || 0) + 1;
    }
    var nums = Array.from(Object.values(map));
    nums.sort((a, b) => a - b);
    while (k > 0 && nums.length && k >= nums[0]) {
        k -= nums.shift();
    }
    return nums.length;
};

Explain:

Sort.

Complexity:

• Time complexity : O(n * log(n)).
• Space complexity : O(n).

Solution 2

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number}
 */
var findLeastNumOfUniqueInts = function(arr, k) {
    var map = {};
    var nums = Array(arr.length + 1).fill(0);
    for (var i = 0; i < arr.length; i++) {
        if (map[arr[i]] === undefined) {
            map[arr[i]] = 1;
        } else {
            nums[map[arr[i]]] -= 1;
            map[arr[i]] += 1;
        }
        nums[map[arr[i]]] += 1;
    }
    var num = 0;
    for (var j = 0; j < nums.length; j++) {
        if (k > 0) {
            var tmp = nums[j];
            nums[j] = Math.max(0, nums[j] - Math.floor(k / j));
            k -= tmp * j;
        }
        num += nums[j];
    }
    return num;
};

Explain:

Counting sort.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).