Coding interview problems › Heaps & Top-K

🔺 Heaps & Top-K Medium

Top K Frequent Elements

Top K Frequent Elements: count with a hash map, then keep a size-k min-heap of frequencies or bucket by count for O(n). Tested Python and a live visual.

Also searched as: k most frequent elements · top k frequent using heap · bucket sort frequency

🔺

Try it live Free

Binary Heap & Priority Queue

Push and pop in the heap lab to see why the smallest entry is always on top; here the heap is ordered by frequency, so the least frequent candidate is the one that gets evicted.

Also useful: Hash Tables

Open the playground →

The problem

Given a list of integers and an integer k, return the k values that appear most often, in any order. You may assume the answer is unique, meaning there is no tie at the k-th place.

Inputnums = [1, 1, 1, 2, 2, 3], k = 2
Output[1, 2]
Inputnums = [4], k = 1
Output[4]

The key insight

This is two small problems. First, count every value with a hash map in one pass. Then pick the k largest counts: a min-heap of size k does that in O(m log k) for m distinct values, because whenever the heap grows past k you throw away the least frequent value so far.

Brute force first: Counting and then sorting every distinct value by frequency is O(m log m), fine in practice, but the heap and bucket methods are what interviewers ask for next.

Step-by-step approach

  1. Count frequencies with collections.Counter(nums).
  2. For each (value, count), push (count, value) onto a min-heap.
  3. Whenever the heap holds more than k entries, pop the smallest count.
  4. The heap now holds the k most frequent values; return them.

Python solution

PYTHON 3tested
import heapq
from collections import Counter


def top_k_frequent(nums, k):
    counts = Counter(nums)                  # value -> frequency
    heap = []                               # min-heap of (count, value)
    for value, c in counts.items():
        heapq.heappush(heap, (c, value))
        if len(heap) > k:
            heapq.heappop(heap)             # drop the least frequent
    return [value for c, value in heap]

Complexity

TimeO(n + m log k)
SpaceO(m + k)

Counting is O(n) for n numbers. Each of the m distinct values is pushed once onto a heap that never exceeds k + 1 entries, costing O(log k) each.

Common mistakes

Frequently asked questions

What is the time and space complexity of Top K Frequent Elements?

With a size-k heap it is O(n + m log k) time for n numbers and m distinct values, and O(m + k) space for the counter and the heap.

How does the O(n) bucket sort solution work?

Make n + 1 buckets where bucket c lists the values that appear exactly c times. Walk the buckets from high to low frequency, collecting values until you have k. It runs in O(n) time and space.

Can I just use Counter.most_common(k)?

Yes, it returns the k most frequent pairs and uses a heap internally for small k. It is a good shortcut in an online test; in an interview, be ready to explain or write the heap version.

What changes if ties are possible?

You need a tie-break rule, for example smaller value first. Encode it in the heap key, such as (count, -value), so the heap evicts the right element.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Heaps & Top-K Binary Heap & Priority Queue lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.