Leetcode 1338: Reduce Array Size to The Half

Input: The input consists of an integer array arr.

Example: arr = [1, 1, 2, 2, 3, 3, 4, 5, 5]

Constraints:

• 2 <= arr.length <= 10^5

• arr.length is even.

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

Output: The output should be the minimum size of the set that can be removed to make at least half of the array elements disappear.

Example: For arr = [1, 1, 2, 2, 3, 3, 4, 5, 5], the output will be 2.

Constraints:

• The returned set should be the smallest set that achieves the goal.

Goal: The goal is to find the minimum set of integers that should be removed to reduce the size of the array by at least half.

Steps:

• 1. Count the frequency of each integer in the array.

• 2. Sort the integers by their frequency in descending order.

• 3. Keep removing integers starting from the most frequent until the total number of removed elements is at least half the size of the array.

• 4. Return the number of integers removed.

Goal: The array size is manageable, but the solution should handle larger inputs efficiently.

Steps:

• 2 <= arr.length <= 10^5

• arr.length is even.

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

Assumptions:

• The array may have duplicate integers.

• The array length is always even.

• Input: Example 1: arr = [1, 1, 2, 2, 3, 3, 4, 5, 5]

• Explanation: Choosing the set {1, 5} will remove at least half of the elements from the array.

• Input: Example 2: arr = [4, 4, 4, 4, 5, 5, 5, 5]

• Explanation: Choosing either {4} or {5} will remove all elements from the array, achieving the goal with the smallest set.

Approach: To solve this problem, count the frequency of each integer, sort the integers by their frequency, and remove the most frequent integers until at least half of the elements are removed.

Observations:

• Removing the most frequent integers will reduce the array size the quickest.

• Sorting the integers by frequency will allow us to efficiently determine the smallest set of integers to remove.

Steps:

• 1. Count the frequency of each element in the array.

• 2. Sort the frequencies in descending order.

• 3. Keep removing elements from the most frequent until half of the array is removed.

• 4. Return the number of distinct elements removed.

Empty Inputs:

• Empty inputs are not valid given the constraints.

Large Inputs:

• Ensure that the approach works efficiently for large arrays up to the size 10^5.

Special Values:

• If one integer appears enough times, removing just that integer might be sufficient.

Constraints:

• Handle arrays where many integers may have the same frequency.

int minSetSize(vector<int>& arr) {
    unordered_map<int, int> mp;
    for(int c: arr) ++mp[c];

    vector<int> frq;
    for(auto [_, fq] : mp) frq.push_back(fq);

    sort(frq.begin(), frq.end());

    int ans = 0, i = frq.size() - 1, half = arr.size()/2, rm = 0;
    while(rm < half) {
        rm += frq[i--];
        ans++;
    }
    return ans;
}

1 : Function Definition

int minSetSize(vector<int>& arr) {

This line defines the function 'minSetSize', which takes a vector of integers 'arr' and returns the minimum number of elements needed to reduce the array by half.

2 : Initialize Frequency Map

    unordered_map<int, int> mp;

We initialize an unordered map 'mp' to store the frequency of each element in the input array.

3 : Count Element Frequencies

    for(int c: arr) ++mp[c];

This loop iterates through each element 'c' in the array and increments its corresponding frequency in the map 'mp'.

4 : Store Frequencies

    vector<int> frq;

We initialize a vector 'frq' to store the frequencies of the elements found in the map 'mp'.

5 : Transfer Frequencies to Vector

    for(auto [_, fq] : mp) frq.push_back(fq);

We iterate through the frequency map and push the frequency values (not the keys) into the 'frq' vector.

6 : Sort Frequencies

    sort(frq.begin(), frq.end());

We sort the frequencies in ascending order so that we can remove the most frequent elements first.

7 : Set Initial Values

    int ans = 0, i = frq.size() - 1, half = arr.size()/2, rm = 0;

Here, we initialize 'ans' to 0 (the count of elements to remove), 'i' to the last index of the frequency vector, 'half' to half the size of the array, and 'rm' to 0 (the count of removed elements).

8 : While Loop

    while(rm < half) {

This while loop runs until we have removed enough elements to reduce the array by half. In each iteration, we remove one of the most frequent elements.

9 : Remove Most Frequent Element

        rm += frq[i--];

We add the frequency of the current most frequent element (at index 'i') to the removed element count 'rm', and decrement the index 'i' to consider the next most frequent element.

10 : Increment Answer

        ans++;

Each time we remove an element, we increment the answer variable 'ans' to track the number of elements removed.

11 : Return Result

    return ans;

Once the while loop finishes, we return the number of elements we need to remove to achieve the goal, stored in 'ans'.

Best Case: O(n log n), where n is the size of the array.

Average Case: O(n log n)

Worst Case: O(n log n)

Description: Sorting the frequencies takes O(n log n), where n is the number of elements in the array.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) for storing the frequency counts of the integers.

Leetcode 1338: Reduce Array Size to The Half

Explore →