Top K Frequent Elements (LC 347) — Frequency + Bucket Sort

What does it solve?

Return the k elements that appear most often. Sorting by frequency is O(N log N); a heap is O(N log k); bucket sort by frequency hits O(N).

Key insight: two stages. First count every value's frequency in a hash map. Then note that a frequency can be at most N, so make N+1 buckets indexed by frequency and drop each value into bucket[freq]. Walk the buckets from highest frequency down, collecting values until you have k. Both passes are linear → O(N).

The core idea

Complexity

Time complexity

O(N)

Counting is O(N); bucketing is O(distinct); reading top-k walks at most N+1 buckets. No comparison sort.

Space complexity

O(N)

The frequency map plus N+1 buckets. A heap variant trades to O(N·log k) time for O(k) space.

Examples & edge cases

Live animation — count frequencies

nums

Frequency map — value → count

{ } empty

Current step detail

— — — result = —

Step — of —

current

—

value

distinct

—

values seen

max freq

—

highest count

picked

—

of k

Select an example and press Play to start.

✓ Done

SpeedMedium

Step-by-step table

C++ implementation

top_k_frequent.cpp

#include <bits/stdc++.h>
using namespace std;

// k most frequent elements via bucket sort by frequency, O(n)
vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int x : nums) freq[x]++;          // 1) count

    int n = nums.size();
    vector<vector<int>> bucket(n + 1); // index = frequency
    for (auto& [val, c] : freq)
        bucket[c].push_back(val);            // 2) bucket by freq

    vector<int> res;
    for (int f = n; f >= 1 && (int)res.size() < k; f--)
        for (int v : bucket[f]) {          // 3) read high → low
            res.push_back(v);
            if ((int)res.size() == k) break;
        }
    return res;
}

int main() {
    vector<int> a = {1,1,1,2,2,3};
    for (int x : topKFrequent(a, 2)) cout << x << " "; // 1 2
    return 0;
}

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem