PYTHON & CODING · QUESTION 90
How do you find the top k most frequent elements?
On this page
Count each value with a hash map, then select the k highest frequencies. Sorting all distinct values costs O(m log m), where m is the number of unique values. A size-k heap can reduce selection to O(m log k), while bucket grouping can achieve O(n) time when frequency bounds and memory are acceptable. Clarify tie behavior and input constraints.
LET'S MAKE IT SIMPLE
First, the idea in plain English
First count how often each item appears. Then rank those counts and keep the k largest. The best selection method depends on how many unique values there are, how small k is, and whether ties need a specific order.
A USEFUL COMPARISON
Picture it this way
A shop counts sales for every product, then chooses the most popular k products for a display. Sorting all products is simple, while a small priority queue is efficient when the shop carries many products but displays only a few.
FOLLOW THE JOURNEY
Count occurrences, then select the largest frequencies
Compare sorting and heap-based selection after frequency counting.
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; Equal frequencies may otherwise produce different valid answers.
Input values feed a frequency map; distinct values are ranked by frequency using sorting or a size-k min-heap to produce the top k.
How to read this visual
This simplified visual highlights the main relationships. In practice, the exact design depends on the requirements; Equal frequencies may otherwise produce different valid answers.
UNDER THE HOOD
How it works, step by step
Count values
Build a mapping from each distinct value to its frequency.
Why it matters: Selection operates on counts rather than repeated input entries.
Choose selection strategy
Sort all unique values or maintain a heap of size k.
Why it matters: The number of unique values and k determine efficiency.
Resolve ties
Apply a deterministic tie-breaker if required by the contract.
Why it matters: Equal frequencies may otherwise produce different valid answers.
OUTSIDE THE TEXTBOOK
A practical example
A service counts error codes in a log window and displays the five most frequent. A Counter provides frequencies; a heap selects five codes without sorting every distinct code. If the dashboard requires stable ordering when counts tie, the code adds an explicit lexical tie-break.
GO A LITTLE DEEPER
Technical details that matter
- Let n be input length and m unique-value count; Counter uses O(m) space.
- A heap takes O(m log k) selection time, while full sorting takes O(m log m).
- Frequency buckets can be linear in n but may use many buckets and need careful tie ordering.
from collections import Counter
import heapq
def top_k(values, k):
counts = Counter(values)
return heapq.nlargest(k, counts, key=counts.get)`Counter` builds frequencies and `heapq.nlargest` selects up to k keys. If tie ordering is part of the contract, include a deterministic secondary key.
MAKE A GOOD CHOICE
When is this useful?
- Finding frequent words, events, or product IDs.
- Building ranked operational dashboards.
- Selecting a small number of leaders from high-cardinality data.
Sort all counts for small inputs or when all ranks are needed. Use streaming sketches for massive data when approximate counts are acceptable.
WATCH OUT FOR
Common misunderstandings
- Sorting the entire input instead of distinct counts.
- Ignoring tie behavior and whether fewer than k items may exist.
- Claiming O(n log k) without defining n, m, and the counting work.
REAL-WORLD TRADE-OFFS
Limitations and failure cases
- Exact counting requires memory proportional to distinct values.
- Top-k ties may need an explicit ordering rule.
- Approximate sketches can mis-rank close frequencies.
WHAT TO REMEMBER
Key takeaways
- 1Count first, then select among distinct values.
- 2Choose sort, heap, or buckets based on k and input size.
- 3Clarify ties, output order, and whether approximation is allowed.
PRACTICE THE FOLLOW-UP
What might an interviewer ask next?
When is a heap better than sorting?
When k is small relative to the number of unique values, a size-k heap can avoid sorting every item. Sorting is simpler when all ranks are needed.
How would you process a stream too large to count exactly?
Use a bounded heavy-hitter or frequency-sketch algorithm if approximate counts are acceptable, and state its error guarantees.
SAY IT OUT LOUD
How to explain this in an interview
“I count each distinct value, then select the k largest frequencies. Sorting all m unique values is O(m log m); a size-k heap is O(m log k), with O(m) counting space. For very large streams I might use an approximate heavy-hitter structure if allowed. I would clarify ties and output ordering before coding.”
Connect this question to the roadmap topic it supports.