Top K Frequent Elements

Intuitionfrequency is already a sorting key

The answer is determined entirely by how often each distinct value appears. Count those appearances first, then rank the distinct values by their counts. A value appearing five times must be considered before one appearing twice, regardless of the values themselves or the order in which they occur in nums.

The frequencies have a useful bounded range: no value can appear more than nums.size times. That means you can create bucket f for every possible frequency f, put each value into the bucket matching its count, and scan from the largest bucket downward. The first k values encountered are exactly the k most frequent values; ties cannot make the answer ambiguous because the problem guarantees a unique answer.

Approach

1. 1Build a frequency map by incrementing the count for every number in nums, because comparing raw array positions cannot reveal which distinct values are frequent.
2. 2Create n + 1 buckets, where n is nums.size, because a value can occur anywhere from once to n times and its frequency will be used directly as an index.
3. 3Place each distinct value in buckets[count], because grouping by exact frequency lets you rank all values without comparing every pair of frequencies.
4. 4Scan the buckets from frequency n down to frequency 1, because a lower-frequency bucket can never contain a better candidate than a nonempty higher-frequency bucket.
5. 5Append values from each visited bucket to the result and stop as soon as its size is k, because the problem asks for k elements and further scanning would do unnecessary work.
6. 6Return the result in the order collected, because the answer may be returned in any order and descending frequency already gives a valid order.

Complexitycounting and bucket placement stay linear

Annotated solutionC++ · bucket sort · one pass per representation of the data

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int x : nums) {
            ++freq[x];
        }

        int n = static_cast<int>(nums.size());
        vector<vector<int>> buckets(n + 1);
        for (const auto& entry : freq) {
            int value = entry.first;
            int count = entry.second;
            buckets[count].push_back(value);
        }

        vector<int> result;
        for (int count = n; count >= 1 && static_cast<int>(result.size()) < k; --count) {
            for (int value : buckets[count]) {
                result.push_back(value);
                if (static_cast<int>(result.size()) == k) {
                    break;
                }
            }
        }

        return result;
    }
};

The bucket index is the central line of the solution: buckets[count]. A value is inserted once after its final count is known, so the later scan never needs to compare two values directly. The second stopping condition matters as well. It prevents the code from collecting extra values from the same bucket when several values share the frequency at which the kth answer is found.

The heap alternativea useful O(n log k) choice when you want bounded selection storage

A min-heap gives another natural solution. First count frequencies, then keep only the best k values seen so far. The heap root is the currently weakest selected value, so whenever a new value is stronger than that root, remove the root and insert the new value. This is not an optimisation over buckets in asymptotic time, but it uses O(k) selection storage instead of storing frequency buckets for every possible count.

#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int x : nums) {
            ++freq[x];
        }

        using Entry = pair<int, int>;
        priority_queue<Entry, vector<Entry>, greater<Entry>> minHeap;

        for (const auto& entry : freq) {
            int value = entry.first;
            int count = entry.second;
            minHeap.push({count, value});
            if (static_cast<int>(minHeap.size()) > k) {
                minHeap.pop();
            }
        }

        vector<int> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second);
            minHeap.pop();
        }
        return result;
    }
};

Common mistakesthe index and the stopping point both carry meaning