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.Example
nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
The number 1 appears 3 times and 2 appears 2 times, making them the two most frequent elements. The number 3 only appears once, so it is not included.
First, count how often each number appears using a hashmap. Then use bucket sort: create an array where the index represents frequency, and each bucket holds the numbers that appear that many times. Walk the buckets from highest frequency down, collecting numbers until you have k elements. This avoids the O(n log n) cost of sorting.
Why this works
You need the top k elements by frequency, but sorting costs O(n log n). Instead, use bucket sort: create an array where position i holds numbers that appear i times. Since no number can appear more than n times, you just walk backwards from the last bucket to grab the most frequent elements first.
Step by step
- Count frequencies — use a hashmap to tally how many times each number appears.
- Place into buckets — create an array of size n+1; put each number into the bucket matching its frequency.
- Collect from the top — iterate from the highest-frequency bucket downward, collecting numbers until you have k.
Time: O(n)
Space: O(n)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
List<Integer>[] buckets = new List[nums.length + 1]; // index = frequency
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
buckets[entry.getValue()].add(entry.getKey());
}
int[] result = new int[k];
int idx = 0;
for (int i = buckets.length - 1; i >= 0 && idx < k; i--) { // highest freq first
for (int num : buckets[i]) {
result[idx++] = num;
if (idx == k) break;
}
}
return result;
}
}
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> count;
for (int num : nums) {
count[num]++;
}
vector<vector<int>> buckets(nums.size() + 1); // index = frequency
for (auto& [num, freq] : count) {
buckets[freq].push_back(num);
}
vector<int> result;
for (int i = buckets.size() - 1; i >= 0 && result.size() < k; i--) { // highest freq first
for (int num : buckets[i]) {
result.push_back(num);
if (result.size() == k) return result;
}
}
return result;
}
};
def topKFrequent(nums: list[int], k: int) -> list[int]:
count = {}
for num in nums:
count[num] = count.get(num, 0) + 1
buckets = [[] for _ in range(len(nums) + 1)] # index = frequency
for num, freq in count.items():
buckets[freq].append(num)
result = []
for i in range(len(buckets) - 1, 0, -1): # walk from highest frequency down
for num in buckets[i]:
result.append(num)
if len(result) == k:
return result
return result