LC-1338 Medium LeetCode

1338. Reduce Array Size to The Half

Array Hash Table Greedy Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 69% Topics: Array, Hash Table, Greedy, Sorting, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

import collections

        
class Solution(object):
    def minSetSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        counting_sort = [0]*len(arr)
        count = collections.Counter(arr)
        for c in count.itervalues():
            counting_sort[c-1] += 1
        result, total = 0, 0
        for c in reversed(xrange(len(arr))):
            if not counting_sort[c]:
                continue
            count = min(counting_sort[c],
                        ((len(arr)+1)//2 - total - 1)//(c+1) + 1)
            result += count
            total += count*(c+1)
            if total >= (len(arr)+1)//2:
                break
        return result

Solution from kamyu104/LeetCode-Solutions · MIT