What is the time complexity of the heap solution?

O(n log k). Counting is O(n), and each of the distinct values costs at most one O(log k) heap operation.

Can this be done in O(n)?

Yes, with bucket sort. Place each value in a bucket indexed by its count, then read buckets from the highest count down.

Why use a min-heap of size k instead of a max-heap?

The root of a min-heap is the smallest of the k best seen so far. A new value only needs one comparison against it to be kept or rejected.

When is sorting the counts simpler?

When k is close to the number of distinct values, sorting at O(m log m) is as good and shorter to write. The heap helps most when k is small.

What does Counter.most_common(k) do?

It uses a heap internally for small k, so it is an acceptable one-line answer. Interviewers usually still want the manual version explained.

How are ties handled?

The problem usually guarantees a unique answer. If not, decide a tie-breaking rule and encode it in the heap tuple.

Top k frequent elements

Interview QuestionsBy Ashish JangraUpdated 25 October 2026

Count, then keep a min-heap of size k. The root is the weakest of the current best k, so one comparison rejects any candidate that cannot beat it — and most of the input is rejected that way. O(n log k) rather than O(n log n), and the gap is real once the number of distinct values is large.

Heaps & top-kCoding problemMedium

Step through it

Speed

What to watch

The heap never grows past k — that is what makes each operation log k.
Most candidates are rejected by one comparison against the root.
The root is the smallest of the kept values, not the largest.

Say this out loud

"Count with a Counter, then keep a min-heap of size k keyed on the count. For each item, if the heap is short push it; otherwise compare against the root and replace only if it is bigger. That is O(n log k). heapq.nlargest does exactly this. If k is close to n I would just sort, and if the counts are small integers bucket sort is O(n)."

import heapq, random, time from collections import Counter random.seed(7) words = [random.randint(0, 40_000) for _ in range(200_000)] counts = Counter(words) k = 10 print("n =", len(words), " distinct =", len(counts), " k =", k) # 1. sort everything, take a slice: O(n log n) t0 = time.perf_counter() by_sort = [w for w, _ in sorted(counts.items(), key=lambda kv: -kv[1])[:k]] a = time.perf_counter() - t0 # 2. a heap of size k: O(n log k) t0 = time.perf_counter() by_heap = [w for w, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])] b = time.perf_counter() - t0

import heapq, random, time from collections import Counter random.seed(7) words = [random.randint(0, 40_000) for _ in range(200_000)] counts = Counter(words) k = 10 # 3. bucket by count: O(n), because a count cannot exceed n def by_buckets(counts, k): if not counts: return [] buckets = [[] for _ in range(max(counts.values()) + 1)] for key, c in counts.items(): buckets[c].append(key) out = [] for c in range(len(buckets) - 1, 0, -1): for key in buckets[c]: out.append(key) if len(out) == k: return out return out t0 = time.perf_counter() by_bucket = by_buckets(counts, k) c = time.perf_counter() - t0 by_sort = [w for w, _ in sorted(counts.items(), key=lambda kv: -kv[1])[:k]] by_heap = [w for w, _ in heapq.nlargest(k, counts.items(), key=lambda kv: kv[1])] print("all three pick the same counts:", sorted(counts[w] for w in by_sort) == sorted(counts[w] for w in by_heap) == sorted(counts[w] for w in by_bucket)) print(f" buckets {c*1000:7.1f} ms O(n), level with the heap at this size")

import heapq, random, time from collections import Counter random.seed(7) words = [random.randint(0, 40_000) for _ in range(200_000)] counts = Counter(words) k = 10 # Where the log k actually comes from: how little ever enters the heap. def top_k(pairs, k): heap = [] entered = skipped = 0 for key, cnt in pairs: if len(heap) < k: heapq.heappush(heap, (cnt, key)); entered += 1 elif cnt > heap[0][0]: heapq.heapreplace(heap, (cnt, key)); entered += 1 else: skipped += 1 # rejected by ONE comparison return sorted(heap, reverse=True), entered, skipped kept, entered, skipped = top_k(counts.items(), k) print() print(f"of {len(counts):,} distinct values:") print(f" {entered:,} ever entered the heap") print(f" {skipped:,} were rejected by a single comparison against the root") print(f" the heap never held more than {k}")

About the author

Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.

Top k frequent elements

Step through it

What to watch

Say this out loud

Overview

Run it

Why the root is the whole trick

The three answers, and when each is right

Quickselect, and why it is usually the wrong answer to give

What the question is testing

Edge cases to raise

Sources and next steps

How the code works

How the code works

Change one thing

Where this runs

Check yourself