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.
Output
An integer array containing the k values with the highest frequencies, in any order.
Constraints
- •
1 <= nums.length <= 10^5 - •
-10^4 <= nums[i] <= 10^4 - •
1 <= k <= number of unique elements in nums - •
The answer is guaranteed to be unique as a set of values
Examples
Example 1
nums = [1, 1, 1, 2, 2, 3], k = 2
[1, 2]Example 2
nums = [1], k = 1
[1]Example 3
nums = [-1, -1, -2, -2, -2, 3], k = 2
[-2, -1]Learning Objectives
- Separate the problem into counting frequencies and selecting the largest counts.
- Use bucket sort to exploit the fact that no frequency can exceed **n**.
- Use a size-**k** min-heap when the number of unique values is large or streaming-like.
- Explain why returning values in any order simplifies the final extraction.
Intuition
Pattern Recognition
The signal is a frequency ranking question: values matter only through how often they appear. Sorting the full array does not directly answer the question, and sorting all unique values by frequency costs O(u log u) for u unique values.
First build a hash map from value to count. Then choose a selection strategy. Bucket sort is linear because frequencies are integers from 1 to n. A size-k min-heap is useful when you want to keep only the current best k values while scanning the frequency map.
Common mistakes
- ×Sorting the original array and assuming adjacent duplicates automatically produce the top k values without a selection step.
- ×Building buckets by value instead of by frequency.
- ×Using a max-heap of all unique values when a size-k min-heap is enough for the heap approach.
- ×Returning frequencies instead of the elements that have those frequencies.
Algorithm Explanation
Key idea
Count each value with a hash map. For the linear approach, create buckets where bucket f contains all values that appear f times. Scan buckets from high frequency to low frequency and collect values until k elements have been selected.
Walkthrough
For nums = [1, 1, 1, 2, 2, 3] and k = 2, the frequency map becomes 1 -> 3, 2 -> 2, 3 -> 1. Put 1 in bucket 3, 2 in bucket 2, and 3 in bucket 1. Scanning from bucket 6 down, the first non-empty bucket gives 1, the next gives 2, and the answer is complete.
Algorithm
- Count every value in frequencyByValue.
- Create an array of buckets with indices from 0 through nums.length.
- For each map entry, append the value to the bucket matching its frequency.
- Scan bucket indices from high to low.
- Add values from each non-empty bucket to the answer.
- Stop as soon as k values have been collected.
Solutions
Solution 1: Bucket sort by frequency
Use this when the input array is available and you want the best asymptotic time. Frequencies are bounded by n, so buckets avoid comparing every unique value.
After counting, frequency becomes the sortable key. Because the maximum frequency is nums.length, an array of lists acts like a counting sort over frequencies.
Step-by-step
- Build frequencyByValue with one pass over nums.
- Allocate nums.length + 1 buckets, where bucket index means frequency.
- Place each unique value into the bucket for its count.
- Walk buckets from largest frequency down to 1.
- Copy values into the answer until exactly k values have been written.
O(n)
O(n)
Counting, bucketing, and scanning the bucket array are all linear in the input size.
Java implementation
Solution 2: Size-k min-heap
Use this when you want to keep only the best k candidates after counting, especially when k is much smaller than the number of unique values.
Maintain a min-heap ordered by frequency. Each heap entry is a value and its count. If the heap grows beyond k, remove the least frequent entry, leaving only the top candidates.
Step-by-step
- Count frequencies in a hash map.
- Push each unique value and frequency into a min-heap ordered by frequency.
- Whenever the heap size exceeds k, remove the smallest frequency.
- After all entries are processed, the heap contains the k most frequent values.
- Pop them into the answer array in any order.
O(n log k)
O(n)
The frequency map stores up to n unique values, while heap operations cost log k each.
Java implementation
Dry Run
Sample input
nums = [1, 1, 1, 2, 2, 3], k = 2. Track counting, bucket placement, and high-to-low extraction.
| step | phase | item | frequency state | selection state |
|---|---|---|---|---|
| 1 | count | 1 | 1 -> 1 | no buckets yet |
| 2 | count | 1 | 1 -> 2 | no buckets yet |
| 3 | count | 1 | 1 -> 3 | no buckets yet |
| 4 | count | 2, 2, 3 | 1 -> 3, 2 -> 2, 3 -> 1 | counting complete |
| 5 | bucket | entries | bucket 3: [1], bucket 2: [2], bucket 1: [3] | answer empty |
| 6 | scan | frequency 3 | bucket 3 has [1] | answer [1] |
| 7 | scan | frequency 2 | bucket 2 has [2] | answer [1, 2] |
Scanning from the highest frequency down collects 1 and 2 before lower-frequency values can enter the answer.
Interview Tips
Name the two phases: count, then select. For the bucket solution, emphasize that frequencies are bounded by n, which is why the bucket array is linear. For the heap solution, emphasize the k-sized heap invariant: after processing any number of unique values, the heap keeps the best k seen so far.
Likely follow-ups
- How would you handle ties if the output had to be sorted by value within the same frequency?
- How would you solve this for a stream where the final array is not stored?
- What changes if **k** is close to the number of unique values?
- How would you return the top **k** frequent words with lexicographic tie-breaking?
Similar Problems
Key Takeaways
- Frequency questions usually split into counting and selecting.
- Bucket sort is linear when the key range is the frequency range **0...n**.
- A size-k min-heap keeps only the best candidates and costs **O(n log k)**.
- The output order is flexible unless the prompt says otherwise.