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.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Solution {
6 public int[] TopKFrequent(int[] nums, int k) {
7 var freqMap = new Dictionary<int, int>();
8 foreach (var num in nums) {
9 if (!freqMap.ContainsKey(num))
10 freqMap[num] = 0;
11 freqMap[num]++;
12 }
13
14 return freqMap.OrderByDescending(x => x.Value).Take(k).Select(x => x.Key).ToArray();
15 }
16
17 public static void Main(string[] args) {
18 int[] nums = new int[] {1, 1, 1, 2, 2, 3};
19 int k = 2;
20 Solution sol = new Solution();
21 int[] result = sol.TopKFrequent(nums, k);
22 Console.WriteLine(string.Join(", ", result));
23 }
24}
25We use a dictionary to count frequencies, then order by descending frequency and take the top k 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.
By clustering elements into frequency buckets, the most frequented elements appear in the last non-empty buckets.