DSA problem
Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. It is guaranteed that the answer is unique — there is no ambiguity in which k values tie for the cutoff frequency.
A correct but slow approach builds a frequency map, sorts the (value, frequency) pairs in descending order of frequency, and slices off the first k. That costs O(n log n) time and is unnecessarily expensive when k is small compared to n.
The canonical heap-based solution avoids sorting the entire frequency table. Count frequencies with a hash map in O(n). Then push entries into a min-heap keyed by frequency of size k: whenever the heap grows beyond k items, pop the least frequent. After processing every distinct value, the heap holds exactly the k most frequent. This runs in O(n log k), which is strictly better when k is small.
An even faster alternative is bucket sort by frequency. Because every frequency is in the range [1, n], we can create n + 1 buckets and place each value into the bucket indexed by its frequency. Reading buckets from high to low and collecting the first k values gives an O(n) solution. The follow-up in the problem statement explicitly asks for an algorithm better than O(n log n), and bucket sort hits the linear-time floor. The heap solution shown below is the most widely used pattern, with bucket sort noted as an alternative.
Examples
nums = [1,1,1,2,2,3], k = 2[1,2]nums = [1], k = 1[1]nums = [4,4,4,5,5,6,6,7], k = 2[4,5]Constraints
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- k is in the range [1, the number of unique elements in the array].
- It is guaranteed that the answer is unique.
- Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.