Greedy Algorithm to Remove Half of the List

Given a list of integers nums, consider an operation where you pick any number e and remove every number in nums equal to e. Return the minimum number of operations required such that the length of nums is reduced by at least half.

Constraints
1 ≤ n ≤ 100,000 where n is the length of nums

Example 1
Input
nums = [7, 9, 9, 7, 3, 4, 5]
Output
2
Explanation
Length of the list is 7, so we need to remove at least 4 elements. We can do this by removing all 7s and 9s.

Example 2
Input
nums = [6, 6, 6, 3, 2, 1]
Output
1
Explanation
Length of the list is 6, so we need to remove at least 3 elements. We can do this by removing all 6s.

Example 3
Input
nums = [1, 2, 3, 4, 5, 6]
Output
3
Explanation
We can delete any 3 numbers in the list.

Greedy Algorithm to Remove Half List

If we sort the array by the number of occurencies in non-ascending order. We then can greedily pick the numbers (that occur most) until the total picked numbers are larger than half. As we are always picking from the largest occurencies to the smallest, we can guarantee that the numbers to pick is always minimal.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def removeHalf(self, nums):
        d = Counter(nums)
        l = len(nums)
        x = sorted(d.values(), reverse=True)
        ans = 0
        z = 0
        for v in x:
            ans += 1
            z += v
            if z * 2 >= l:
                break
        return ans

class Solution:
    def removeHalf(self, nums):
        d = Counter(nums)
        l = len(nums)
        x = sorted(d.values(), reverse=True)
        ans = 0
        z = 0
        for v in x:
            ans += 1
            z += v
            if z * 2 >= l:
                break
        return ans

The time complexity is O(NLogN) as we need to sort the array. The space complexity is O(N) as we are using Counter (or other hash map) to keep tracking the occurencies of all numbers.

–EOF (The Ultimate Computing & Technology Blog) —