13. Top K Frequent Elements
Given an integer array nums and an integer k, return the k values that occur most often in nums. You may return them in any order.
The tests guarantee that the answer is unique: there is never a tie in frequency between the k-th most frequent value and the next one.
Input: nums = [4,4,4,6,6,9], k = 2 Output: [4,6]
Explanation: 4 occurs three times and 6 twice; 9 occurs only once.
Input: nums = [7], k = 1 Output: [7]
Input: nums = [5,3,5,2,3,5,1], k = 2 Output: [5,3]
Explanation: Frequencies are 5 → 3, 3 → 2, 2 → 1, 1 → 1.
Constraints
1 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <=the number of distinct values innums- The answer is unique.
Follow-up: Can you beat O(n log n), where n is the length of the array?
💡 Hint 1
First count how many times each value occurs with a hash map.
💡 Hint 2
Sorting the distinct values by count costs O(m log m). A min-heap of size k brings that to O(m log k).
💡 Hint 3
A frequency is always between 1 and n. Put each value into a bucket indexed by its count, then read buckets from the highest count down until you have k values.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Count occurrences with a hash map. Then use bucket sort by frequency: create n + 1 buckets where buckets[c] holds every value that occurs exactly c times. Walk the buckets from n down to 1, collecting values until you have k of them. Because frequencies are bounded by n, this avoids sorting entirely.
function topKFrequent(nums, k) {
const count = new Map();
for (const x of nums) count.set(x, (count.get(x) ?? 0) + 1);
const buckets = Array.from({ length: nums.length + 1 }, () => []);
for (const [value, c] of count) buckets[c].push(value);
const result = [];
for (let c = nums.length; c > 0 && result.length < k; c--) {
for (const value of buckets[c]) {
if (result.length < k) result.push(value);
}
}
return result;
}class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums) count.merge(x, 1, Integer::sum);
List<List<Integer>> buckets = new ArrayList<>();
for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
for (Map.Entry<Integer, Integer> e : count.entrySet()) buckets.get(e.getValue()).add(e.getKey());
int[] result = new int[k];
int filled = 0;
for (int c = nums.length; c > 0 && filled < k; c--) {
for (int value : buckets.get(c)) {
if (filled < k) result[filled++] = value;
}
}
return result;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
function topKFrequent(nums, k) {
}Run your code to see results here.