CODING CHALLENGE · N°27

Top-K Frequent Elements

Medium Hash MapHeapsInterview Classic

Count, then rank — the two-step pattern behind trending topics, hot keys, and a thousand interview questions. A hash map does the counting; the ranking is where heaps, buckets, or a simple sort earn their keep.

The problem

Given nums, a list of integers, and k, return the k most frequent values, ordered by frequency descending; break frequency ties by the smaller value first. You may assume k ≤ the number of distinct values.

EXAMPLE 1

Input nums = [1,1,1,2,2,3], k = 2

Output [1, 2]

1 appears 3×, 2 appears 2×

EXAMPLE 2

Input nums = [4,4,5,5,6], k = 2

Output [4, 5]

tie at 2× → smaller value first

EXAMPLE 3

Input nums = [7], k = 1

Output [7]

trivial but a real edge case

CONSTRAINTS

Order: frequency descending, then value ascending on ties.
k ≤ number of distinct values in nums.
Aim for O(n log n) or better (bucket sort by count gets O(n)).

SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement top_k_frequent(nums, k) → the k most frequent values, frequency descending, ties broken by smaller value.

HINTS — 4 IDEAS

Count with a dict / Map first — one pass.
Then sort the distinct values by (-count, value) and take the first k.
The tie-break is exactly what the tuple sort key encodes.
For the O(n) flex: bucket values by count (counts are ≤ n), then walk buckets high to low.

CPython · WebAssembly

Approach, complexity & discussion — open after you solve

The approach

Two steps: count frequencies with a hash map, then select the top k. For selection, keep a min-heap of size k — push each (count, item) and pop the smallest whenever the heap exceeds k, so what remains is the k most frequent (O(n log k)). Or bucket sort: index an array by frequency (0…n) and read buckets from the high end down for O(n).

Complexity

Min-heap: time O(n log k), space O(n + k). Bucket sort: time O(n), space O(n).

Common mistakes

Fully sorting all the counts (O(n log n)) when a size-k heap or bucket sort is enough.
Using a max-heap of all n elements (O(n log n)) instead of a min-heap capped at k.
Mishandling ties or an empty input — decide the tie-break and guard k > number of distinct items.

Where this shows up

“Most frequent” is everywhere: trending topics, top search queries, hot cache keys, word clouds, analytics dashboards. The keep-only-the-best-k-seen pattern (a bounded min-heap) generalizes to any top-k-from-a-stream problem where you cannot hold or sort everything — the same idea behind streaming heavy-hitter algorithms.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA