Blind 75 Visualized

#27 · Heap / Priority Queue

Top K Frequent Elements

Given an integer array and an integer k, return the k most frequent elements, in any order. The algorithm should be better than O(n log n).

MediumLeetCode
  • Active
  • Found
  • Window
  • Visited
  • Rejected
step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Frequency table (hash map)

Counts how many times each value occurs in one pass. After it, the problem is no longer about the array but about m distinct (value, count) pairs.

Memory layout

Hash buckets of entries; O(m) memory where m is the number of distinct values. Counting costs O(n) expected.

OperationCost
increment a countO(1) expected
count the whole arrayO(n)

Min-heap (priority queue) of size k

A binary heap where the smallest element is on top. Keeping at most k elements, with the least frequent at the root, means the root is always the next one to evict: after all values are offered the heap holds exactly the k most frequent.

Memory layout

A contiguous array where the children of index i are at 2i+1 and 2i+2: no pointers and good cache behavior. Size is capped at k.

OperationCost
push / popO(log k)
whole selectionO(m log k) time, O(k) space

Frequency buckets / quickselect

Counts are integers between 1 and n, so values can be bucketed by count and read from the top bucket down (O(n)). Alternatively quickselect partitions the m distinct values around a pivot, discarding the part that cannot contain the k-th rank (O(m) on average).

Memory layout

Buckets: an array of n + 1 lists. Quickselect: in-place swaps in the array of distinct values.

OperationCost
bucket sortO(n) time, O(n) space
quickselectO(m) average, O(m²) worst case

Why it fits

  • We need only the top k, not a full ordering, so any structure that avoids sorting everything (a size-k heap, buckets, or selection) beats O(m log m).
  • A heap capped at k elements makes each decision O(log k), and for small k that is nearly constant: O(n log k) overall.
  • Because counts are small integers bounded by n, a bucket array turns "sort by frequency" into a counting sort: linear time.

Why alternatives degrade

Sort all (value, count) pairs:
O(m log m), which the problem explicitly asks us to beat; most of that work orders values we then discard.
Max-heap of all m values:
Building and popping k times costs O(m + k log m): fine, but it keeps m elements in memory where a size-k heap keeps k.
Sorting the original array first:
O(n log n) just to group equal values, when a hash map groups them in O(n).

Four approaches, from naive to production

1 · beginner

Count, sort, slice

time O(n + m log m)space O(m)

Count every value, sort the (value, count) pairs by count in descending order, and return the first k.

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;
    vector<pair<int, int>> entries(count.begin(), count.end());
    sort(entries.begin(), entries.end(), [](auto& a, auto& b) { return a.second > b.second; });
    vector<int> result;
    for (int i = 0; i < k; i++) result.push_back(entries[i].first);
    return result;
}

Flaws & bottlenecks

  • Sorts all m distinct values although only the top k matter.
  • O(m log m) in the worst case (all values distinct, so m = n): O(n log n), which the problem asks us to beat.
  • Allocates a full list of pairs.

Interviewer cross-questions

Can you avoid sorting everything?

Say: Yes. A min-heap of size k keeps only the k best so far (O(m log k)), bucket sort by count is O(n), and quickselect is O(m) on average.

What if there are ties for the k-th place?

Say: The problem guarantees the answer is unique. Without that guarantee you would have to define a tie-break, because sorting alone would keep an arbitrary tied value.

What is m in the worst case?

Say: m = n when all values are distinct. Then sorting costs O(n log n).

2 · intermediate

Min-heap of size k

time O(n + m log k)space O(m + k)

After counting, offer each distinct value to a min-heap ordered by count. Whenever the heap grows beyond k, evict the least frequent value.

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> heap;
    for (auto& [n, c] : count) {
        heap.push({c, n});
        if ((int)heap.size() > k) heap.pop();
    }
    vector<int> result;
    while (!heap.empty()) { result.push_back(heap.top().second); heap.pop(); }
    return result;
}

Flaws & bottlenecks

  • Needs a heap implementation (JavaScript has none built in).
  • log k per distinct value: still more than the O(n) that buckets achieve.
  • The result comes out in heap order, not sorted by frequency: sort it (O(k log k)) if order is required.

Interviewer cross-questions

Why a MIN-heap to find the largest k?

Say: The root is the weakest of the current top k, the first to be replaced. Each new value is compared with it in O(1) and replaces it in O(log k) if better. A max-heap would give the single best, not a cap on size.

When is the heap better than buckets?

Say: When the data is a stream or too large to bucket by count: memory is O(k) beyond the counts, and k is usually tiny. It also works for arbitrary scores, not just small integer counts.

What is the complexity when k is close to m?

Say: It approaches O(m log m): the heap holds almost everything. Then sorting, or selecting the n − k LEAST frequent instead, is the better strategy.

3 · advanced

Bucket sort by frequency

time O(n)space O(n)

A value can occur at most n times, so create n + 1 buckets indexed by count, drop each value into its bucket, and read buckets from the highest count down until k values are collected.

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;
    vector<vector<int>> buckets(nums.size() + 1);
    for (auto& [n, c] : count) buckets[c].push_back(n);
    vector<int> result;
    for (int c = (int)buckets.size() - 1; c > 0 && (int)result.size() < k; c--) {
        result.insert(result.end(), buckets[c].begin(), buckets[c].end());
    }
    if ((int)result.size() > k) result.resize(k);
    return result;
}

Flaws & bottlenecks

  • Allocates n + 1 buckets even when only a few counts occur.
  • Relies on counts being small integers; it does not work for arbitrary real-valued scores.
  • A bucket can overshoot k (several values tied at the cutoff), so the result is sliced to k at the end.

Interviewer cross-questions

Why is this O(n) and not O(n log n)?

Say: Counting is O(n); placing each of the m distinct values into a bucket is O(1) each; scanning the buckets visits at most n + 1 of them. Nothing is compared or sorted.

What happens with ties at the k-th place?

Say: A whole bucket is appended, which may push the result above k. The problem guarantees a unique answer; otherwise you would slice (arbitrary tie-break) or decide on a rule.

How would it behave on a stream?

Say: Counts keep changing, so values would have to move between buckets (remove from bucket c, add to c + 1): O(1) with linked buckets (the idea behind an LFU cache).

4 · expert

Quickselect on distinct values

time O(n + m) averagespace O(m)

Instead of sorting or heaping, partition the distinct values around a pivot by frequency (descending). The pivot lands at its final rank; recurse into only the side that contains rank k.

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;
    vector<int> uniq; for (auto& [n, c] : count) uniq.push_back(n);
    auto freq = [&](int i) { return count[uniq[i]]; };
    int left = 0;
    int right = (int)uniq.size() - 1;
    while (left < right) {
        int pivotFreq = freq(right);
        int store = left;
        for (int i = left; i < right; i++) {
            if (freq(i) > pivotFreq) {
                swap(uniq[store], uniq[i]);
                store++;
            }
        }
        swap(uniq[store], uniq[right]);
        if (store == k - 1) break;
        if (store < k - 1) left = store + 1;
        else right = store - 1;
    }
    return vector<int>(uniq.begin(), uniq.begin() + k);
}

Flaws & bottlenecks

  • Worst case O(m²) with bad pivots (e.g. a last-element pivot on already-sorted input); production code picks a random or median-of-three pivot.
  • Reorders the array in place and returns values in no particular order.
  • More code and more edge cases (k = m, equal frequencies) than the heap or bucket solutions.

Interviewer cross-questions

Why is the average O(m)?

Say: Each partition costs linear time in the window and, with a random pivot, the window shrinks geometrically in expectation: m + m/2 + m/4 + … = O(m).

How do you avoid the O(m²) worst case?

Say: Choose the pivot randomly (or median of three), or use introselect / median of medians for a guaranteed linear bound. A fixed last-element pivot is shown here for clarity.

Which would you ship?

Say: For interviews and most production code the heap (clear and robust) or buckets (linear and simple). Quickselect is the answer when you want the best average time and can accept in-place mutation.

Synchronized code walkthrough

Showing: Count, sort, slice — shares the player above; click any step to jump.

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    for (int n : nums) count[n]++;
    vector<pair<int, int>> entries(count.begin(), count.end());
    sort(entries.begin(), entries.end(), [](auto& a, auto& b) { return a.second > b.second; });
    vector<int> result;
    for (int i = 0; i < k; i++) result.push_back(entries[i].first);
    return result;
}