Return the k values that appear most often. Count with a hash map, then either sift the top k with a heap in O(n log k) — or skip sorting entirely and bucket by frequency for a clean O(n) answer.
Given an integer array nums and an integer k, return the k most frequently occurring values (in any order). Example: nums = [1,1,1,2,2,3], k = 2 → the value 1 appears 3×, 2 appears 2×, 3 appears 1×, so the answer is [1, 2]. The problem guarantees the answer is unique.
n times, so every frequency lives in the range 1…n. That means you can use the count itself as an array index: put each value into buckets[count]. Reading the buckets from high index to low gives values in descending frequency order — no comparison sort, no heap needed.Map<value, count>so you know each value's frequency.n + 1 empty lists. For each (value, count), append the value to buckets[count] — the index is the frequency.1, collecting values until you have k of them, then stop. Higher index = more frequent, so you naturally take the top k first.buckets[3]means "all values that occurred 3 times," and a single bucket can hold several values (ties). Size it to n + 1 because a count can be as large as n and index 0 is never used.Heap: count frequencies, then push (value) keyed by frequency into a min-heap capped at size k; whenever it overflows, pop the smallest. The heap ends holding exactly the k most frequent values, in O(n log k)time. It's the natural "top k" tool and is easy to describe in an interview. A full sort of distinct frequencies would be O(n log n).
Bucket sort: because every frequency is an integer in 1…n, you can bucket by count and read off the top k in O(n) time and O(n) space — asymptotically optimal since you must at least read the input.
2 most frequent values in an array of 6 numbers. Phase 1: build a frequency map in one pass.function topKFrequent(nums: number[], k: number): number[] {
// 1) Count every value in one pass.
const freq = new Map<number, number>();
for (const n of nums) {
freq.set(n, (freq.get(n) ?? 0) + 1);
}
// 2) Bucket sort: buckets[c] = all values seen exactly c times.
// A value's count is at most nums.length, so we need that many slots.
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [val, count] of freq) {
buckets[count].push(val);
}
// 3) Walk buckets from the highest count down, collecting k values.
const res: number[] = [];
for (let c = buckets.length - 1; c >= 1 && res.length < k; c--) {
for (const val of buckets[c]) {
res.push(val);
if (res.length === k) return res;
}
}
return res;
}nums builds a Map from each value to how many times it appears. The ?? 0 seeds first-time keys.nums.length + 1 empty arrays. For each (val, count), push val into buckets[count]. We never use index 0 (no value appears zero times), and the max possible count is nums.length.res.length === k, then return immediately — no need to scan the rest.O(n log k).| "k most frequent / top k" | count map → size-k heap (O(n log k)) |
| want strictly O(n) | bucket by frequency (counts ≤ n) |
| frequency used as an index | buckets[count], walk high → low |
| "kth largest / k closest" | size-k min-heap, evict smallest |
const freq = new Map<number, number>();
for (const n of nums) freq.set(n, (freq.get(n) ?? 0) + 1);
const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
for (const [v, c] of freq) buckets[c].push(v);
const res: number[] = [];
for (let c = buckets.length - 1; c >= 1 && res.length < k; c--) {
for (const v of buckets[c]) {
res.push(v);
if (res.length === k) return res;
}
}
return res;