Most Frequent Elements
Receives an array of integers and a number k, and returns the k most frequent values ordered from highest to lowest frequency. It runs in O(n) using bucket sort: first it counts every value's frequency in a hash map, then it scatters each value into a bucket indexed by its frequency (so all values that appear the same number of times share a bucket), and finally it reads the buckets from the highest frequency down, collecting values until it has k of them. Returns a new array with the k most frequent values, most frequent first; when several values tie in frequency any order between the tied ones is valid. If k is greater than or equal to the number of distinct values it returns every distinct value, and an empty input yields an empty array.
Visualization
- Input
- Result
Algorithm code
// Most Frequent Elements — a single pure function. Receives an array of
// integers and a number k, and returns the k most frequent values ordered
// from highest to lowest frequency, using bucket sort to run in O(n): count
// each value's frequency, scatter values into buckets indexed by frequency,
// then read the buckets from the highest frequency down.
/**
* @param {number[]} arr - array of integers
* @param {number} k - how many of the most frequent values to return
* @returns {number[]} the k most frequent values, most frequent first
*/
export function topKFrequent(arr, k) {
const counts = new Map();
for (const value of arr) {
counts.set(value, (counts.get(value) ?? 0) + 1);
}
const buckets = Array.from({ length: arr.length + 1 }, () => []);
for (const [value, count] of counts) {
buckets[count].push(value);
}
const result = [];
for (let freq = buckets.length - 1; freq >= 1; freq -= 1) {
for (const value of buckets[freq]) {
if (result.length >= k) {
return result;
}
result.push(value);
}
}
return result;
}FUNCTION topKFrequent(arr, k):
counts ← empty map
FOR EACH value IN arr:
counts[value] ← counts[value] + 1
buckets ← array of (length(arr) + 1) empty lists
FOR EACH (value, count) IN counts:
append value TO buckets[count]
result ← empty list
FOR freq ← length(buckets) - 1 DOWN TO 1:
FOR EACH value IN buckets[freq]:
IF length(result) ≥ k:
RETURN result
append value TO result
RETURN result