Top K Frequent Elements — Bucket Sort O(n) [Google, Meta, Amazon]

Problem Statement

Given integer array nums and integer k, return the k most frequent elements.

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

Approach 1 — Min-Heap O(n log k)
Approach 2 — Bucket Sort O(n) ✅ Optimal
C++ Solution (Bucket Sort)
Java Solution
Python Solution
JavaScript Solution
Complexity: O(n) time (bucket sort), O(n) space

Approach 1 — Min-Heap O(n log k)

Count frequencies, use min-heap of size k.

Approach 2 — Bucket Sort O(n) ✅ Optimal

Since max frequency ≤ n, create n+1 buckets. Put each number in bucket freq[num]. Walk buckets from high to low.

C++ Solution (Bucket Sort)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> freq;
        for (int n : nums) freq[n]++;
        vector<vector<int>> buckets(nums.size()+1);
        for (auto& [v, c] : freq) buckets[c].push_back(v);
        vector<int> res;
        for (int i = (int)buckets.size()-1; i >= 0 && (int)res.size() < k; i--)
            for (int v : buckets[i]) if ((int)res.size() < k) res.push_back(v);
        return res;
    }
};

Java Solution

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> freq = new HashMap<>();
        for (int n : nums) freq.merge(n,1,Integer::sum);
        List<Integer>[] buckets = new List[nums.length+1];
        for (int v : freq.keySet()) {
            int c = freq.get(v);
            if (buckets[c]==null) buckets[c]=new ArrayList<>();
            buckets[c].add(v);
        }
        int[] res = new int[k]; int idx=0;
        for (int i=buckets.length-1;i>=0&&idx<k;i--)
            if (buckets[i]!=null) for (int v:buckets[i]) if(idx<k) res[idx++]=v;
        return res;
    }
}

Python Solution

from collections import Counter
def topKFrequent(nums, k):
    freq = Counter(nums)
    buckets = [[] for _ in range(len(nums)+1)]
    for v, c in freq.items(): buckets[c].append(v)
    res = []
    for bucket in reversed(buckets):
        for v in bucket:
            res.append(v)
            if len(res) == k: return res
    return res

JavaScript Solution

function topKFrequent(nums, k) {
    const freq = new Map();
    for (const n of nums) freq.set(n, (freq.get(n)||0)+1);
    const buckets = Array.from({length: nums.length+1}, ()=>[]);
    for (const [v,c] of freq) buckets[c].push(v);
    const res = [];
    for (let i = buckets.length-1; i>=0 && res.length<k; i--)
        for (const v of buckets[i]) if(res.length<k) res.push(v);
    return res;
}