Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104k is in the range [1, the number of unique elements in the array].Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
The goal of Top K Frequent Elements is to return the k numbers that appear most frequently in an array. A common first step is to build a frequency map using a HashMap or dictionary, where each number is mapped to its occurrence count. Once frequencies are known, the challenge becomes efficiently selecting the top k elements.
One efficient strategy is using a min-heap (priority queue). After computing frequencies, push elements into a heap ordered by frequency and keep the heap size at k. This ensures the smallest frequency among the top candidates is removed whenever the heap grows beyond k.
Another optimized approach is bucket sort, where indices represent frequencies and each bucket stores numbers with that frequency. This allows collecting the most frequent elements in near linear time. Advanced solutions may also use Quickselect to partition elements based on frequency. Depending on the method used, the solution can achieve O(n log k) or even O(n) time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Min Heap (Priority Queue) | O(n log k) | O(n) |
| Bucket Sort | O(n) | O(n) |
| Quickselect | Average O(n) | O(n) |
NeetCode
This approach uses a hash map to count the frequency of each element. We then use a min-heap to keep track of the top k elements.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
1from collections import Counter
2import heapq
3
4def topKFrequent(nums, k):
5 count = Counter(nums)
6 return heapq.nlargest(k, count.keys(), key=count.get)
7
8if __name__ == '__main__':
9 nums = [1,1,1,2,2,3]
10 k = 2
11 print(topKFrequent(nums, k))
12We use Python's collections.Counter and heapq.nlargest functions to efficiently get the top k frequent elements.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, using the bucket sort approach. Since the maximum possible frequency of any element is n, you can create frequency buckets and iterate from the highest frequency down to collect the top k elements in linear time.
Yes, this problem is frequently asked in FAANG and other top tech company interviews. It tests knowledge of hash maps, heaps, and efficient selection techniques like bucket sort or quickselect.
A common optimal approach is using a frequency hash map combined with a min-heap of size k. This keeps track of the k most frequent elements while iterating through the frequencies. It runs in O(n log k) time and works efficiently for large inputs.
A hash map is used to count element frequencies, and a heap or priority queue is typically used to track the top k frequent items. Alternatively, bucket sort can be used to achieve linear time complexity by grouping numbers based on their frequency.
We manually record each element's frequency and sort the list based on counts into a frequency bucket. Then, we retrieve the top k elements.