Least Number of Unique Integers after K Removals — LeetCode 1481 Python Solution
MediumGreedyArrayHash TableCountingSorting
- Problem
- #1481
- Pattern
- Greedy
- Reading time
- 2 min
- Source
- leetcode.com
The problem
Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.
Example
- Input
- arr = [5,5,4], k = 1
- Output
- 1
- Explanation
- Remove the single 4, only 5 is left.
Python solution
Python
class Solution:
def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
cnt = Counter(arr)
for i, v in enumerate(sorted(cnt.values())):
k -= v
if k < 0:
return len(cnt) - i
return 0Complexity
| Measure | Complexity |
|---|---|
| Time | O(n \times \log n) |
| Space | O(n), where n is the length of the array arr auxiliary |
Pattern: Greedy
Take the locally best option every time — when you can prove that never costs you later. LeetCode 1481. Least Number of Unique Integers after K Removals is filed here because LeetCode tags it Greedy, which is the vocabulary this hub collects.
The greedy guide has the Python template for the pattern and the 346 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1481. Least Number of Unique Integers after K Removals?
- LeetCode 1481. Least Number of Unique Integers after K Removals is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1481. Least Number of Unique Integers after K Removals?
- The Python solution on this page runs in O(n \times \log n).
- What is the space complexity of LeetCode 1481. Least Number of Unique Integers after K Removals?
- The Python solution on this page uses O(n), where n is the length of the array arr auxiliary space.
- What topics does LeetCode 1481. Least Number of Unique Integers after K Removals cover?
- LeetCode 1481. Least Number of Unique Integers after K Removals is tagged Greedy, Array, Hash Table, Counting and Sorting on LeetCode.