Back to solutions

Top K Frequent Elements

MediumArrays

Return the k most frequent values.

Open problem
Constraints
  • 1 <= n <= 10^5
  • k is in [1, number of distinct values]

Bucket by frequency

Time O(n)Space O(n)

Count each value's frequency, then place values into buckets indexed by frequency (0..n). Scan buckets from the highest frequency down, collecting values until you have k. This avoids a full sort and runs in linear time.

Key terms
frequency map:
How many times each distinct value appears.
bucket sort by count:
Grouping values by their frequency so the most frequent are read first.
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;
    int n = nums.size();
    vector<vector<int>> buckets(n + 1);
    for (auto& [v, f] : freq) buckets[f].push_back(v);
    vector<int> res;
    for (int f = n; f >= 1 && (int)res.size() < k; f--)
        for (int v : buckets[f]) if ((int)res.size() < k) res.push_back(v);
    sort(res.begin(), res.end());
    return res;
}
Step by step
  1. Count frequencies of every value.
  2. Create buckets where bucket[f] lists values appearing exactly f times.
  3. Walk f from n down to 1, collecting values until k are gathered.
  4. Return those values (sorted here for determinism).