Top K Frequent Elements
The key idea
Count how often each value appears, then you only need the
k values with the largest counts. A size-k min-heap keyed by frequency keeps just those k while discarding everything smaller, and bucketing by frequency removes the sort entirely for an O(n) pass.Problem
You are given an integer array nums and an integer k. Return the k most frequent elements — the k values that appear the most times in nums. You may return the answer in any order.
The count of an element is how many times it occurs in nums. The answer is guaranteed to be unique, so there is no ambiguity about which k values to return.
Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
kis in the range [1, the number of unique elements innums]- The answer is guaranteed to be unique (the set of the top
kfrequent elements is unique)
Examples
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Input: nums = [1], k = 1
Output: [1]
Complexity
Time: O(n log k) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Heap / Priority Queue problems
- Find K Pairs with Smallest SumsMEDIUM
- Find Median from Data StreamHARD
- IPOHARD
- K Closest Points to OriginMEDIUM
- Kth Largest Element in a StreamEASY
- Kth Largest Element in an ArrayMEDIUM
- Last Stone WeightEASY
- Maximum Subsequence ScoreMEDIUM
- Meeting Rooms IIMEDIUM
- Meeting Rooms IIIHARD
- Merge k Sorted ListsHARD
- Minimum Interval to Include Each QueryHARD