MediumNo. 1338
Reduce Array Size to The Half — LeetCode 1338 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Hash Table, Sorting, 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
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 ansComplexity
- Time
- O(n × log n)
- Space · auxiliary
- O(n)
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.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0621 | Task Scheduler | Medium |
| 0632 | Smallest Range Covering Elements from K Lists | Hard |
| 1054 | Distant Barcodes | Medium |
| 2357 | Make Array Zero by Subtracting Equal Amounts | Easy |
| 2813 | Maximum Elegance of a K-Length Subsequence | Hard |
| 0347 | Top K Frequent Elements | Medium |
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 × 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.