Reduce Array Size to The Half with JS solved using dictionary

Given an array arr.  You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

Solution

iterate over an array and store the number of repetitive integers in the dictionary

generate an array of integers and sort

keep adding values starting with the largest till we reach half of the array

Time Complexity: O(n*log(n)) <- due to sorting

/**
 * @param {number[]} arr
 * @return {number}
 */
var minSetSize = function(arr) {
    let freq = {}; 
    for (let i = 0; i<arr.length; i++) { // O(n)
        if (freq[arr[i]] > 0) {
            freq[arr[i]] = freq[arr[i]] + 1;
        } else {
            freq[arr[i]] = 1;
        }
    }
    
    let sorted = [];
    for(var key in freq) {
        //insert into a sorted array
        sorted.push(freq[key]);
}
    sorted.sort();
    let result = 0;
    let count = 0;
    for (let i=sorted.length-1; i>=0; i--) {
        count++;
        result = result + sorted[i];
        if (result >= arr.length / 2) {
            break;
        }
    }

    return count;
};