← Index

Arrays & Hashing

Top K Frequent ElementsMedium

Given an integer array and an integer k, return the k most frequent elements, in any order.

Examples

Approach

Counting frequencies is the easy part — a Map does that in one pass. The interesting decision is how to pull out the top k: sorting all unique values by frequency works but costs O(n log n) for a job that doesn't need full ordering. Bucket sort skips the sort entirely — since frequency can never exceed the array's length, use frequency itself as an array index. Walk the buckets from highest frequency down and collect values until you have k.

Complexity — best & worst case

Code

// Given an array of integers and an integer k, return the k most
// frequent elements, in any order.

// --- Sorting approach: count, then sort by frequency ---
function topKFrequentSort(nums, k) {
  const counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);

  return [...counts.entries()]
    .sort((a, b) => b[1] - a[1]) // sort descending by count
    .slice(0, k)
    .map(([value]) => value);
}

// --- Optimal: bucket sort by frequency, O(n) instead of O(n log n) ---
// Frequency can never exceed nums.length, so we can use frequency
// itself as an array index — no comparison sort needed at all.
function 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 [value, freq] of counts) {
    buckets[freq].push(value);
  }

  const result = [];
  for (let freq = buckets.length - 1; freq >= 0 && result.length < k; freq--) {
    for (const value of buckets[freq]) {
      result.push(value);
      if (result.length === k) break;
    }
  }
  return result;
}

// --- Example Usage ---
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [1, 2]
console.log(topKFrequentSort([1, 1, 1, 2, 2, 3], 2)); // [1, 2]
console.log(topKFrequent([1], 1)); // [1]