Given an integer array nums and an integer k, return the k values that occur most often. The answer is guaranteed to be unique, and you may return it in any order. Try to beat O(n log n).
Example 1
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1 appears 3 times and 2 appears 2 times, more than any other value.
Example 2
Input: nums = [1], k = 1
Output: [1]
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- k is between 1 and the number of distinct values
- The top k set is unique
Hints
Frequently asked at: Amazon, Meta, Google, Uber, Oracle
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
After counting with a hash map, sorting all distinct values by frequency costs O(n log n). A min-heap of size k brings it to O(n log k). Bucket sort does even better: since no value can appear more than n times, create buckets 0..n, put each value in the bucket of its count, and collect values from the highest bucket down until we have k.
Algorithm
- Count each value with a hash map.
- Create
n + 1empty buckets; put each value intobucket[count]. - Walk buckets from
ndown to 1, adding values to the result. - Stop as soon as the result has
kvalues.
Time:
O(n)Space: O(n)Interview tip: Be ready to discuss the heap version too: it is O(n log k) and works on a stream, while bucket sort needs to know
n up front. Interviewers often ask for both.class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = Counter(nums) bucket = [[] for _ in range(len(nums) + 1)] # bucket[f] = values seen f times for v, f in count.items(): bucket[f].append(v) ans = [] for f in range(len(nums), 0, -1): for v in bucket[f]: ans.append(v) if len(ans) == k: return ans return ansCtrl + Enter runs the examples