Heap / Priority Queue
LC #347Medium
Top K Frequent Elements
Heap / Priority Queue
AmazonMetaGoogleBloombergMicrosoftProblem
Return the k most frequent elements. Answer can be in any order. Must be better than O(n log n).
arrayheaphash-mapbucket-sort
Constraints
- ›1 ≤ nums.length ≤ 10⁵
- ›-10⁴ ≤ nums[i] ≤ 10⁴
- ›1 ≤ k ≤ number of unique elements
- ›O(n log n) guaranteed answer; O(n) possible with bucket sort
Example
Input
nums = [1, 1, 1, 2, 2, 3], k = 2Output
[1, 2]Why
1 appears 3 times, 2 appears 2 times. Top 2 most frequent.