Top k frequent elements
MediumUnlock detailed company stats for this questionUpgrade
Given an array of n numbers and a positive integer K, find the K numbers that appear most frequently in the array. If there is a tie, any set of K numbers can be returned.
Given an integer array nums and an integer k, return the k values that appear most often. You can return them in any order. The answer is guaranteed to be unique.
Example 1
Input: nums = [1, 1, 1, 2, 2, 3], k = 2 Output: [1, 2]
1 appears three times and 2 appears twice.
Example 2
Input: nums = [1], k = 1 Output: [1]
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^4kis between1and the number of distinct values innums.- The set of
kmost frequent values is unique.
Approach
Start by counting each value with a hash map. Now you need the k values with the highest counts. Sorting the counts works in O(n log n) time, and a min-heap capped at k values brings it down to O(n log k). You can go further because the counts are small whole numbers: no value can appear more than n times. Put each value into a bucket indexed by its count, then walk the buckets from n down to 1, collecting values until you have k.
Steps
- Count each value in
nums. - Create
n + 1empty buckets and put each value in the bucket matching its count. - Walk the buckets from count
ndown to1, adding values to the result. - Return the result as soon as it holds
kvalues.
Complexity
- Time:
O(n). Counting, filling the buckets and reading them back are each linear. - Space:
O(n), for the counts and the buckets.
Common mistakes
- Sorting
numsitself instead of the counts. The order ofnumssays nothing about how often each value appears. - Taking every value from a bucket without checking how many you still need. Stop as soon as you have exactly
kvalues.
Interview experiences
3 sharedRelated courses

Course

Course




