How hard is LeetCode 1338. Reduce Array Size to The Half?

LeetCode 1338. Reduce Array Size to The Half is rated Medium on LeetCode.

What is the time complexity of LeetCode 1338. Reduce Array Size to The Half?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1338. Reduce Array Size to The Half?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1338. Reduce Array Size to The Half cover?

LeetCode 1338. Reduce Array Size to The Half is tagged Greedy, Array, Hash Table, Sorting and Heap (Priority Queue) on LeetCode.

Reduce Array Size to The Half — LeetCode 1338 Python Solution

MediumGreedyArrayHash TableSortingHeap (Priority Queue)

Problem: #1338
Pattern: Heap / Priority Queue
Reading time: 2 min
Source: leetcode.com

The problem

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Example

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).

Python solution

Python

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        cnt = Counter(arr)
        ans = m = 0
        for _, v in cnt.most_common():
            m += v
            ans += 1
            if m * 2 >= len(arr):
                break
        return ans

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1338. Reduce Array Size to The Half is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1338. Reduce Array Size to The Half?: LeetCode 1338. Reduce Array Size to The Half is rated Medium on LeetCode.
What is the time complexity of LeetCode 1338. Reduce Array Size to The Half?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1338. Reduce Array Size to The Half?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1338. Reduce Array Size to The Half cover?: LeetCode 1338. Reduce Array Size to The Half is tagged Greedy, Array, Hash Table, Sorting and Heap (Priority Queue) on LeetCode.