< Back





1338. Reduce Array Size to The Half

Given an integer array, we're asked to return the minimum size of the set so that at least half of
the integers from the original array are removed - at least half, so we can remove more.
Interpreting this, we just need to remove the most frequent elements and stop as soon as we reach
half of the original size remaining. We'll use a greedy approach.

Instead of using a max heap or sorting again, we'll use counting to place each integer into buckets
of frequency. We also find out what the max frequency is, so we can start our iteration from that.
Our target is half the size of the original list.

While our target is greater than 0, we select a number of elements to remove, starting with the most
frequent element. We'll choose the minimum between how many elements are in this bucket of frequency
vs. how many elements of this frequency we need to remove to reach our target.

After this selection, we add to our answer the number of elements we've removed, and we update the
target, decrementing the number of elements removed from the input. We also decrement our bucket
index.

The solution is as follows:


  from collections import Counter
  from math import ceil

  class Solution:
      def minSetSize(self, arr: List[int]) -> int:
          freq = Counter(arr)
          max_freq = max(freq.values())
          freq_count = Counter(freq.values())
          ans, target, i = 0, len(arr) // 2, max_freq

          while target > 0:
              remove = min(freq_count[i], ceil(target / i))
              ans += remove
              target -= remove * i
              i -= 1

          return ans


_ Time Complexity:

  O(n) - Where n is the length of the input.

_ Space Complexity:

  O(n) - Our dictionary of counts contains at most n elements.