Top K Frequent Elements

Problem

Given an array, return k most frequent elements. Guaranteed: answer is unique.

Two approaches:

Counter + min-heap of size k — O(n log k)
Bucket sort by frequency — O(n)

Solutions

// C — sort by frequency

// C++ — min-heap approach
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    for (int n : nums) cnt[n]++;
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> minH;
    for (auto& [val, freq] : cnt) {
        minH.push({freq, val});
        if ((int)minH.size() > k) minH.pop();
    }
    vector<int> res;
    while (!minH.empty()) { res.push_back(minH.top().second); minH.pop(); }
    return res;
}

// Java
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int n : nums) cnt.merge(n, 1, Integer::sum);
    PriorityQueue<int[]> minH = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    for (var e : cnt.entrySet()) {
        minH.offer(new int[]{e.getValue(), e.getKey()});
        if (minH.size() > k) minH.poll();
    }
    int[] res = new int[k];
    for (int i = k-1; i >= 0; i--) res[i] = minH.poll()[1];
    return res;
}

// JavaScript — bucket sort O(n)
function topKFrequent(nums, k) {
    const cnt = new Map();
    for (const n of nums) cnt.set(n, (cnt.get(n) || 0) + 1);
    const buckets = Array.from({length: nums.length + 1}, () => []);
    for (const [val, freq] of cnt) buckets[freq].push(val);
    const result = [];
    for (let i = buckets.length - 1; i >= 0 && result.length < k; i--)
        result.push(...buckets[i]);
    return result.slice(0, k);
}

# Python — bucket sort O(n)
from collections import Counter

def topKFrequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]
    for val, freq in count.items():
        buckets[freq].append(val)
    result = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            break
    return result[:k]

Complexity

Heap: O(n log k)
Bucket Sort: O(n) — frequency bounded by array length

Key Insight

Bucket sort exploits the fact that frequency ≤ n. Iterate buckets from high to low, collect until we have k elements.