Problem of The Day: Reduce Array Size to The Half

Problem Statement

leetcode problem link

Brute Force approach [Accepted]

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        counter = Counter(arr)
        total_elems = len(arr)
        half = total_elems // 2
        curr_set = set()
        sorted_arr = sorted(list(counter.items()), key=lambda x: -x[1])

        for k, v in sorted_arr:
            if total_elems <= half:
                break
            curr_set.add(k)
            total_elems -= v

        return len(curr_set)

Approach 1: Sorting

def minSetSize(self, arr: List[int]) -> int:

    # Sort the input numbers.
    arr.sort()

    # Generate the counts array.
    counts = []
    current_run = 1
    for i in range(1, len(arr)):
        if arr[i] == arr[i - 1]:
            current_run += 1
            continue
        counts.append(current_run)
        current_run = 1
    counts.append(current_run)

    # Reverse sort the counts.
    counts.sort(reverse=True)

    # Remove numbers until at least half are removed.
    numbers_removed_from_arr = 0
    set_size = 0
    for count in counts:
        numbers_removed_from_arr += count
        set_size += 1
        if (numbers_removed_from_arr >= len(arr) // 2):
            break

    return set_size

Approach 2: Hashing/ Counting

def minSetSize(self, arr: List[int]) -> int:

    # In Python, we can use the built-in Counter class.
    counts = collections.Counter(arr)

    # Extract the counts in reverse-sorted order.
    # most_common gives (number, count) pairs, reverse sorted on count.
    counts = [count for number, count in counts.most_common()]

    # Remove numbers until at least half are removed.
    total_removed = 0
    set_size = 0
    for count in counts:
        total_removed += count
        set_size += 1
        if (total_removed >= len(arr) // 2):
            break

    return set_size