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.
Problem Overview: You receive an integer array and an integer k. The task is to return the k most frequent elements in the array. Order does not matter, but the algorithm must be efficient since the input size can be large.
Frequency problems usually start with counting occurrences. The main challenge is extracting the top k elements efficiently without sorting the entire dataset. Two common strategies are a heap-based approach and bucket sort.
Approach 1: Hash Map + Min-Heap (O(n log k) time, O(n) space)
First count how many times each number appears using a hash table. This converts the original array problem into a frequency lookup like {number -> count}. Next, maintain a min-heap of size k using a priority queue. Iterate through the frequency map and push (frequency, value) pairs into the heap. Whenever the heap size exceeds k, remove the smallest frequency element. This keeps only the top k frequent elements in the heap. The complexity is O(n log k) because each heap insertion or removal costs log k, and you perform it for up to n unique elements.
Approach 2: Bucket Sort (O(n) time, O(n) space)
Bucket sort removes the need for a heap entirely. Start by counting frequencies using a hash map. The maximum frequency of any number cannot exceed n, so create an array of buckets where the index represents frequency. Each bucket stores the numbers that appear that many times. After building the buckets, iterate from the highest frequency bucket downwards and collect numbers until you gather k elements. This works because frequencies map directly to indices. The approach runs in O(n) time since both counting and bucket traversal are linear.
Approach 3: Quickselect on Frequencies (Average O(n) time, O(n) space)
Another strategy is applying Quickselect, similar to finding the kth largest element. Build a frequency map, convert it into a list of pairs, and partition the list based on frequency. Each partition step moves higher-frequency elements toward the front until the top k region is identified. Average complexity is O(n), though worst-case becomes O(n²). This approach avoids extra structures like heaps or buckets but is more complex to implement correctly.
Recommended for interviews: The hash map + heap solution is the most commonly expected approach. It demonstrates clear understanding of counting with a array traversal and efficient top-k extraction using a priority queue. Bucket sort is even faster at O(n), and strong candidates often mention it as the optimal solution when frequency bounds allow it.
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.
We use a frequency map to track occurrences of each number. Then, we create a struct array for frequencies, sort it, and return the top k elements.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
This approach involves using bucket sort where we create buckets for frequency counts and then extract the top k frequent elements.
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.
Time Complexity: O(n + k).
Space Complexity: O(n).
We can use a hash table cnt to count the occurrence of each element, and then use a min heap (priority queue) to store the top k frequent elements.
First, we traverse the array once to count the occurrence of each element. Then, we iterate through the hash table, storing each element and its count into the min heap. If the size of the min heap exceeds k, we pop the top element of the heap to ensure the heap size is always k.
Finally, we pop the elements from the min heap one by one and place them into the result array.
The time complexity is O(n log k), and the space complexity is O(k). Here, n is the length of the array.
| Approach | Complexity |
|---|---|
| Using a Hash Map and Min-Heap | Time Complexity: O(n log n) due to sorting. |
| Using Bucket Sort | Time Complexity: O(n + k). |
| Hash Table + Priority Queue (Min Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map + Min-Heap | O(n log k) | O(n) | General solution when you need top-k elements efficiently without sorting everything |
| Bucket Sort | O(n) | O(n) | Best when frequency range is bounded by n and you want linear time |
| Quickselect | Average O(n), worst O(n²) | O(n) | Useful when avoiding heaps and implementing selection algorithms |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 880,987 views views
Watch 9 more video solutions →Practice Top K Frequent Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor