Problem statement

https://leetcode.com/problems/reduce-array-size-to-the-half/

Solution

Consider example [3,3,5,5,5,2,2,7,3,3] What we need to do in this problem is:

  1. Calculate frequency of each number, we can do it with Counter(), here we have frequencies [1, 2, 3, 4].
  2. Sort frequencies in decreasing order, because we need to take biggest one first: we have [4, 3, 2, 1]
  3. Evaluate cumulative sums: we have [4, 7, 9, 10]: so, we can remove 4 elements if we remove 1 value, 7 if we remove 2, 9 if we remove 3 and 10 if we remove 4.
  4. Now, we need to find the first element in this array, which is more than half of size. We check this condition for each element and in the end return index of True element + 1, because we need to shift index.

Complexity

Time complexity is O(n log n), because we do one sort and then do some linear passes. Space complexity is O(n).

Code

class Solution:
    def minSetSize(self, A):
        return [2*i >= len(A) for i in accumulate(sorted(Counter(A).values())[::-1])].index(True) + 1

Remark

Actually, step when we sort frequencies of elements can be done in O(n) as well, using the problem 347. Top K Frequent Elements.