How do you find the top K frequent elements?

Q: How do you find the top K frequent elements?

**Target Audience:** Beginners preparing for coding interviews — you need Python lists, dicts and loops; heaps are explained on the linked page. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged `📌 Interview term:` with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the **Verified** section is copied from that run. ## 1. Why This Even Matters — A Story First A music app wants to show "Your top 5 songs this year". It has a log of every play — one line per play, 200,000 lines for a keen listener. Answering the question takes two separate jobs: 1. **Tally.** Go through the log once and keep a running count per song, like tick marks on a sheet with one row per song. 2. **Pick the winners.** From that sheet of counts, pick the 5 r

The problem

Question presented to candidate: "Given a list of integers and a number k, return the k values that appear most often. If two values appear the same number of times, put the smaller value first. Write it in Python and tell me the complexity."

What a strong answer should cover:

Two steps: count with a hash map in O(n), then pick the k biggest counts.
Three ways to pick: sort the m distinct values (O(m log m)), a size-k min-heap (O(m log k)), or bucket sort by count (O(n)) because a count is at most n.
Ties: encode the rule in the key — here the heap key (count, -value) makes the weakest entry the lowest count, then the larger value.
Edge cases: k equal to the number of distinct values, ties at the cut-off, negative numbers.
Python specifics: collections.Counter, and that Counter.most_common(k) breaks ties by first appearance, not by value; heapq is a min-heap, so tuples (count, -value) give the right weakest-first order; heapq.nlargest(k, counts, key=...) as the one-liner.

Clarifying questions expected:

How should ties be ordered, and must the result be sorted by frequency?
Is k always at most the number of distinct values?

Code / implementation expected: Yes — Counter plus a size-k heapq, and the bucket-sort version if asked for O(n), in Python.

heap
top-k

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you need Python lists, dicts and loops; heaps are explained on the linked page.
Difficulty: Medium
Language: Python 3

How to read this doc: every idea is explained in plain words first. When a word appears that an interviewer will expect you to know, it is tagged 📌 Interview term: with a one-line definition, and every tagged term is collected in the Quick Glossary at the end. Every program on this page was actually run, and the output in the Verified section is copied from that run.

1. Why This Even Matters — A Story First

A music app wants to show "Your top 5 songs this year". It has a log of every play — one line per play, 200,000 lines for a keen listener. Answering the question takes two separate jobs:

Tally. Go through the log once and keep a running count per song, like tick mark

The solution is hidden so you can try first

13 min read · 12 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonTop K frequent with a hash map + size-k min-heap (ties: smaller value first)