Overview

Given an integer array and an integer k, return the k most frequent elements. The answer may be returned in any order.

Implement topKFrequent(nums, k).

Constraints

• Input is a non-empty array of integers and a positive integer k.
• k is always valid: 1 ≤ k ≤ number of unique elements.
• The answer is guaranteed to be unique (no ties at the k-th boundary).
• Aim for better than $O(n \log n)$ — a bucket sort approach gives $O(n)$.

Examples

topKFrequent([1, 1, 1, 2, 2, 3], 2);  // [1, 2]
topKFrequent([1], 1);                  // [1]
topKFrequent([4, 4, 4, 6, 6, 2], 1);  // [4]
topKFrequent([1, 2, 2, 3, 3, 3], 3);  // [3, 2, 1] (any order)

Notes

• Frequency map first: count occurrences of each element in $O(n)$.
• Bucket sort approach: create an array of buckets where index = frequency. Elements with the same frequency go into the same bucket. Then iterate from the highest frequency bucket down, collecting elements until you have k results.
• Alternatively, use a min-heap of size k for $O(n \log k)$.
• The result order doesn't matter — only the set of elements matters.

Solution

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

  // Bucket sort: index = frequency
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }

  const result = [];
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }

  return result.slice(0, k);
}

Resources

• Top K Frequent Elements — LeetCode
• Bucket Sort — Wikipedia