Top K Frequent Elements

Difficulty: Medium

You're given a list of numbers and a number k. Find the k numbers that occur most often in the list.

Return them as a list, in any order. You can assume there's always exactly one valid answer for which values make up the top k most frequent ones.

Examples

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1, 2]

1 appears 3 times and 2 appears 2 times - both occur more often than 3, which appears only once.

Input: nums = [1], k = 1
Output: [1]

Input: nums = [4,4,4,6,6,7], k = 2
Output: [4, 6]

4 appears 3 times, 6 appears 2 times - both more often than 7.

Constraints

  • 1 <= nums.length <= 10^5

  • k is always valid: 1 <= k <= number of distinct values in nums.

Approach

No matter the approach, the first thing you need is a count of how often each number appears - a hash map handles that in one pass.

From there, the simplest next step is to sort the numbers by their frequency and take the top k. That's correct, but full sorting is more work than this problem actually needs.

A faster approach takes advantage of one fact: a frequency can never be larger than the length of the list. That means you can create an array of "buckets," where the bucket at index f holds every number that occurs exactly f times. Filling the buckets takes one pass; reading them off from the highest index down, until you've collected k numbers, gives the answer without ever fully sorting anything.

Solutions

Brute Force - Sort by Frequency

Count how often each number occurs using a hash map, then sort those counts from highest to lowest and take the first k numbers.

function topKFrequent(nums, k) {
  const counts = new Map();
  for (const num of nums) {
    counts.set(num, (counts.get(num) || 0) + 1);
  }

  const sorted = [...counts.entries()].sort((a, b) => b[1] - a[1]);

  return sorted.slice(0, k).map((entry) => entry[0]);
}

Time: O(n log n) · Space: O(n)

Optimal - Bucket Sort

Count how often each number occurs, same as before. Then, instead of sorting, create an array of buckets indexed by frequency - bucket[3] holds every number that appears exactly 3 times, and so on. Reading the buckets from the highest frequency down and collecting numbers gives the top k without any sorting.

function topKFrequent(nums, k) {
  const counts = new Map();
  for (const num of nums) {
    counts.set(num, (counts.get(num) || 0) + 1);
  }

  // buckets[freq] = list of numbers that occur exactly "freq" times
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, freq] of counts.entries()) {
    buckets[freq].push(num);
  }

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

  return result;
}

Time: O(n) · Space: O(n)