Reduce Array Size to The Half

class Solution {
    public int minimumSize(int[] array) {
        
        Map<Integer, Integer> frequency = new HashMap<>();
        int highestFreq = 0;
        for (int value : array) {
            if (!frequency.containsKey(value)) {
                frequency.put(value, 0);
            }
            int updatedFreq = frequency.get(value) + 1;
            frequency.put(value, updatedFreq);
            highestFreq = Math.max(highestFreq, updatedFreq);
        }
        
        // Create buckets for frequency counts.
        int[] frequencyBuckets = new int[highestFreq + 1];
        for (int freq : frequency.values()) {
            frequencyBuckets[freq]++;
        }
 
        // Calculate required removals.
        int resultSize = 0;
        int toRemove = array.length / 2;
        int currentFreq = highestFreq;
        while (toRemove > 0) {
            int needed = toRemove / currentFreq;
            if (toRemove % currentFreq != 0) {
                needed++;
            }
            int increaseCount = Math.min(frequencyBuckets[currentFreq], needed);
            resultSize += increaseCount;
            toRemove -= increaseCount * currentFreq;
            currentFreq--;
        }
        
        return resultSize;        
    }
}

The solution provided addresses the problem of reducing the size of an array by at least half by removing the least number of unique elements based on their frequencies. Below is the summary of the solution approach implemented in Java:

1. Utilize a HashMap called frequency to store each unique element of the array as keys and their corresponding counts as values.
2. Iterate through the given array and update the frequency map with the count of each element. Simultaneously, keep track of the maximum frequency (highestFreq) of any single element.
3. Create an integer array frequencyBuckets where the index represents the frequency of elements and each value at that index represents how many elements have that frequency.
4. Populate frequencyBuckets by iterating over the frequency values.
5. To determine the minimum number of unique elements to remove, start from the highest frequency and calculate how many elements of that frequency need to be removed to reduce the array's size by half.
6. Keep decrementing the number of elements needed to be removed (toRemove) and the current frequency from which elements are being removed (currentFreq), until the rest of the array size is reduced by at least half.
7. The value returned by the function, resultSize, indicates the minimum set of unique elements that needs to be removed.

This solution effectively maps element frequencies, leverages the counting sort principle via frequency buckets, and utilizes a greedy strategy from the highest frequencies downward to minimize the number of unique elements removed, ensuring the array size is reduced by at least half.

class FrequencyCounter {
    _frequencyMap = new Map();

    increment(item) {
        if (!this._frequencyMap.has(item)) {
            this._frequencyMap.set(item, 0);
        }
        this._frequencyMap.set(item, this._frequencyMap.get(item) + 1);
        return this._frequencyMap.get(item);
    }

    getValues() {
        return this._frequencyMap.values();
    }
}

var findMinSetSize = function(arr) {
    const frequencyCounter = new FrequencyCounter();

    let highestFrequency = 0;
    for (const element of arr) {
        const updatedCount = frequencyCounter.increment(element);
        highestFrequency = Math.max(updatedCount, highestFrequency);
    }

    if (highestFrequency > arr.length / 2) {
        return 1;
    }

    const frequencyBuckets = Array.from({ length: highestFrequency + 1 }, () => 0);

    for (const count of frequencyCounter.getValues()) {
        frequencyBuckets[count] += 1;
    }

    let requiredSetSize = 0;
    let remainToRemove = Math.floor(arr.length / 2);
    let currentHighest = highestFrequency;

    while (remainToRemove > 0) {
        const needFromBucket = Math.ceil(remainToRemove / currentHighest);
        const addToSetSize = Math.min(frequencyBuckets[currentHighest], needFromBucket);
        requiredSetSize += addToSetSize;
        remainToRemove -= addToSetSize * currentHighest;
        currentHighest -= 1;
    }

    return requiredSetSize;
}

The JavaScript solution for reducing the size of an array to half involves a multi-step process that focuses on counting the frequency of each element and then using this data to determine the minimum set of elements that can represent at least half of the array. Here’s how the solution breaks down:

1. Define a FrequencyCounter class to manage the frequency of each element in the array. This class uses a Map to store elements as keys and their frequencies as values. The class has two methods:

   • increment(item): Increases the frequency count of an item by one. If the item is not present in the map, it initializes the count.
   • getValues(): Returns all frequency values from the map.

2. Write a function findMinSetSize that takes an array arr as input and utilizes the FrequencyCounter to calculate and return the minimum set size that can represent at least half of the elements from the input array.

3. Iterate over each element in the array, updating the frequency of each element using the increment method of FrequencyCounter. During this iteration, also keep track of the highestFrequency of any single element.

4. Immediately return a value of 1 if any single element's frequency exceeds half of the total array length.

5. Create a frequency distribution array, frequencyBuckets, where each index represents how many elements have that frequency.

6. Populate frequencyBuckets by iterating over the values from the frequency counter. Each index in frequencyBuckets accumulates counts of elements that have frequencies corresponding to that index.

7. Determine the required set size (requiredSetSize) by evaluating each frequency bucket, starting from the highest. The process continues until half of the array elements are removed. This is done by calculating how many elements are needed from each bucket to meet the requirement of removing half of the array's elements, adjusting the count of remainToRemove for each bucket utilized.

By the end of these steps, the result will be the minimum number of different elements needed to make sure that at least half of the array's elements can be discarded by frequency, effectively reducing the array's size by at least half.