[LeetCode] 347. Top K Frequent Elements

🧠 Remember: “Count, then collect the tallest.”

The problem — 20 seconds

nums = [1, 1, 1, 2, 2, 3], k = 2 → [1, 2]. Return the k most frequent elements — answer order does not matter, and k is always valid.

Original on LeetCode

Split the job in two. First count — every sighting grows a bar. Then rank — skim the k tallest. Two phases, two tools; the counting is forced, only the ranking is a choice.

Your first instinct

Sort the unique values by frequency and slice:

freq: dict[int, int] = {}
for x in nums:
    freq[x] = freq.get(x, 0) + 1
ranked = sorted(freq, key=freq.get, reverse=True)
return ranked[:k]

Perfectly clear — but the sort costs O(u log u) for u uniques, and the problem demands better than O(n log n). The insight: we never needed a total order, only the top k. A heap (nlargest, O(u log k)) or bucket-by-count (O(n)) both exploit that.

The turning point

Counting and selecting are separate jobs with separate budgets. Counting is unavoidably O(n) — every element must be seen once. Selection only needs the peaks, so pour counts into buckets indexed by frequency (max bucket n), then walk down from the top until k elements are collected. No comparisons between also-rans, ever.

Watch it work

Press Play. Phase 1 grows the race-chart bars one sighting at a time; Phase 2 lights up the two tallest in green.

Interactive visual · Frequency Race

Count everything, crown the tallest

Think of bars growing like a live race chart: every sighting adds one block. When counting ends, skim the k tallest bars — those are your answer.

nums

Step 1 / 1 Speed

1freq: dict[int, int] = {} # value -> height

2for x in nums: freq[x] = freq.get(x, 0) + 1 # grow bars

3top = sorted(freq, key=freq.get, reverse=True)[:k]

4return top # the k tallest

Quick check — make it stick

What decides the winners?

🧠 Memory hook: “Count, then collect the tallest.” Counting and ranking are separate jobs.

What the code is really saying

from collections import Counter
from typing import List


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)  # Phase 1: grow the bars
        return [x for x, _ in freq.most_common(k)]  # Phase 2: skim the tallest

most_common(k) is a heap nlargest inside — O(u log k), interview-safe. For strict O(n), bucket values by count and walk buckets down from n until k are gathered.

Why it works

Invariant after Phase 1: freq[x] is the exact occurrence count of every value — the bar chart is truth. Selection then only compares heights, so the k collected are precisely the k most frequent. Counting touches each element once; ranking never looks at the input again.

Time O(n + u log k) with a heap · O(n) with buckets, space O(n).

🧠 Remember

Top K → “Count, then collect the tallest.” Counting is forced; ranking is where you save.

🔁 Try this: k equals the number of unique elements — what must the answer be, without running anything? (Hint: every bar gets crowned.)