Top K Frequent Elements
Problem Statement
Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned in any order.
Input
An integer array nums and an integer k asking for the k values with highest frequency.
Output
An integer array containing the k most frequent values, in any order.
Constraints
- •
1 <= nums.length <= 100000 - •
-10000 <= nums[i] <= 10000 - •
1 <= k <= number of unique values in nums
Examples
Example 1
nums = [1,1,1,2,2,3], k = 2
[1,2]Example 2
nums = [1], k = 1
[1]Learning Objectives
- Separate frequency counting from top-k selection.
- Order heap candidates by frequency rather than by numeric value.
- Use a size-k min-heap to evict the least frequent retained value.
- Compare heap selection with bucket sort when frequencies are bounded by n.
Intuition
Pattern Recognition
The signal is top k frequent, which is a two-stage problem: first compress the array into counts, then select the k highest counts. Once each unique value has a frequency, the problem becomes the same fixed-size top-k pattern as k-th largest, except the priority is frequency.
The trap is ordering by the element value instead of its count. A value like 100 is not better than 1 unless it appears more often. Another common trap is sorting every unique value by frequency; that is simple, but a size-k min-heap avoids full sorting when k is small.
Common mistakes
- ×Building a heap over raw array values before counting frequencies.
- ×Comparing numbers by value rather than by their frequency in the map.
- ×Keeping a max-heap of all unique values and paying more than O(m log k), where m is the number of unique values.
- ×Forgetting that the output order is irrelevant unless the platform asks otherwise.
Algorithm Explanation
Key idea
Count every value with a hash map. Then scan the unique values with a min-heap ordered by frequency. The heap stores the current k most frequent values; its root is the least frequent among the retained winners. When a new candidate makes the heap too large, popping the root removes the weakest retained frequency.
Heap walkthrough
Use nums = [1,1,1,2,2,3] and k = 2. Counting gives 1 -> 3, 2 -> 2, and 3 -> 1. Process value 1 first; the heap becomes [1:3]. Process 2; the heap becomes [2:2,1:3], with 2 at the root because it has the smaller frequency. Process 3; push to get [3:1,1:3,2:2], then pop 3 because the heap has size three. The heap returns to [2:2,1:3], so the retained values are 1 and 2.
Algorithm
- Build a hash map from value to frequency.
- Create a min-heap of values, comparing two values by their map frequencies.
- Push each unique value into the heap.
- If the heap size exceeds k, pop the least frequent retained value.
- Poll the remaining heap values into the result array.
Solutions
Solution 1: Frequency map with size-k min-heap
Use this when k is smaller than the number of unique values and you want the heap pattern that generalises to streaming or large domains.
Count values first, then keep only the k highest-frequency keys in a min-heap. The root is the least frequent retained key, so it is the one to discard when the heap grows too large.
Step-by-step
- Count each value in a HashMap.
- Create a PriorityQueue whose comparator reads frequencies from the map.
- Offer every unique value into the heap.
- Whenever the heap size exceeds k, poll the lowest-frequency key.
- Move the remaining heap keys into an answer array and return it.
O(n log k)
O(n)
Counting stores up to n unique values, while heap operations keep at most k + 1 keys and cost O(log k).
Java implementation
Solution 2: Bucket sort by frequency
Use this when you want O(n) time and can allocate buckets for frequencies from 0 through n.
A value can appear at most n times, so frequencies are bounded. Place each value into the bucket for its frequency, then scan buckets from high frequency down until k values have been collected.
Step-by-step
- Count every value in a hash map.
- Create n + 1 buckets, where bucket f stores values that appear f times.
- Put each unique value into its frequency bucket.
- Scan buckets from n down to 1.
- Add values to the answer until exactly k values have been collected.
O(n)
O(n)
The map, buckets, and result together use linear space; scanning all buckets is linear.
Java implementation
Dry Run
Sample input
nums = [1,1,1,2,2,3], k = 2. First count frequencies, then track the frequency-ordered min-heap.
| candidate | frequency | heap after push | action | retained values |
|---|---|---|---|---|
| 1 | 3 | [1:3] | size <= k, keep it | [1] |
| 2 | 2 | [2:2,1:3] | size <= k, keep it | [2,1] |
| 3 | 1 | [3:1,1:3,2:2] | pop 3 | [2,1] |
The heap keeps the two highest frequencies: 1 with count 3 and 2 with count 2. The output can be [1,2] or [2,1].
Interview Tips
Make the priority explicit: the heap is ordered by frequency, not by value. If k is close to the number of unique values, full sorting is acceptable but not as pattern-focused. If asked for linear time, use the bounded frequency range to introduce bucket sort.
Likely follow-ups
- How would you handle a stream where values arrive continuously and top k is queried repeatedly?
- How would you break ties if the output had to be sorted by value?
- What changes if the input is too large to fit in memory?
- How would you return the top k words instead of integers?
Similar Problems
Key Takeaways
- Top K Frequent is count first, select second.
- The heap comparator must read frequency, not numeric value.
- A size-k min-heap gives O(n log k) selection after the counts are built.
- Bucket sort reaches O(n) by using frequency as a bounded index.