The problem
Given an integer array nums and an integer k, return the k values that appear most often. The answer is guaranteed to be unique, and may be returned in any order.
Examples
01
- Input
nums = [1, 1, 1, 2, 2, 3], k = 2
- Output
[1, 2]
02
- Input
nums = [1], k = 1
- Output
[1]
Constraints
- 1 ≤ nums.length ≤ 10⁵
- −10⁴ ≤ nums[i] ≤ 10⁴
kis between 1 and the number of distinct values.
The idea
First count how often each value appears, with a hash map. Then we need the values with the largest counts — and sorting them would cost n log n.
But a count can only be between 1 and n. So make n + 1 “buckets”: bucket f holds every value that appears exactly f times. Walking the buckets from the highest down hands out values from most frequent to least; stop after k. This is bucket sort, and it is linear.
- Time
- O(n) — count, fill buckets, read buckets
- Space
- O(n) — the counts and the buckets
Solution · every language run against every case
class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = Counter(nums) # buckets[f] holds every number that appears exactly f times. buckets = [[] for _ in range(len(nums) + 1)] for x, f in count.items(): buckets[f].append(x) out = [] for f in range(len(buckets) - 1, 0, -1): for x in buckets[f]: out.append(x) if len(out) == k: return out return out