Problem
Given an integer array nums and integer k, return the k most frequent elements.
Example
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]Solution
Bucket sort by frequency. Frequencies range from 1 to n, so we can place each value in a bucket indexed by its count.
def top_k_frequent(nums, k):
counts = {}
for n in nums: counts[n] = counts.get(n, 0) + 1
buckets = [[] for _ in range(len(nums) + 1)]
for num, cnt in counts.items():
buckets[cnt].append(num)
result = []
for i in range(len(buckets) - 1, -1, -1):
for num in buckets[i]:
result.append(num)
if len(result) == k: return result
return resultfunction topKFrequent(nums, k) {
const counts = new Map();
for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
const buckets = Array.from({length: nums.length + 1}, () => []);
for (const [num, cnt] of counts) buckets[cnt].push(num);
const result = [];
for (let i = buckets.length - 1; i >= 0; i--) {
for (const num of buckets[i]) {
result.push(num);
if (result.length === k) return result;
}
}
return result;
}vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> counts;
for (int n : nums) counts[n]++;
vector<vector<int>> buckets(nums.size() + 1);
for (auto& [num, cnt] : counts) buckets[cnt].push_back(num);
vector<int> result;
for (int i = buckets.size() - 1; i >= 0 && result.size() < k; i--) {
for (int num : buckets[i]) {
result.push_back(num);
if (result.size() == k) return result;
}
}
return result;
}public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> counts = new HashMap<>();
for (int n : nums) counts.merge(n, 1, Integer::sum);
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
for (var e : counts.entrySet()) buckets.get(e.getValue()).add(e.getKey());
int[] result = new int[k];
int idx = 0;
for (int i = buckets.size() - 1; i >= 0 && idx < k; i--) {
for (int num : buckets.get(i)) {
if (idx < k) result[idx++] = num;
}
}
return result;
}Complexity
- Time: O(n)
- Space: O(n)
Explanation
Bucket sort beats heap (O(n log k)) here. Frequencies are bounded by array length, so each goes in a fixed-size bucket array.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?