Top-K Frequent Elements

Start from brute force

The obvious approach counts each distinct value by scanning the whole list: sorted(set(nums), key=lambda v: (-nums.count(v), v))[:k]. It works because nums.count(v) is exactly the frequency of v and the key encodes the required order. But every count is a full pass, so it costs O(n · d) time for n numbers with d distinct values, which is O(n²) when most values are distinct, plus O(d) space for the set. With 100,000 numbers, all distinct, that is ten billion element comparisons, where a single counting pass touches each number once.

The approach

Counting once turns n numbers into d (value, count) pairs, and the ranking needs nothing else. The reference builds counts in one pass with counts[x] = counts.get(x, 0) + 1, so afterwards counts[v] is exactly how often v occurs. One sort of the distinct values with the key (-counts[v], v) then orders them by frequency descending and, on equal frequency, by smaller value, which is precisely the output order, so ranked[:k] is the answer. Negating the count lets a single ascending sort run the two keys in opposite directions; the TypeScript version gets the same order from the comparator (counts.get(b)! - counts.get(a)!) || a - b.

The sort is over the d distinct values, not the n inputs, which is why it beats sorting the list. When d is large and k is small, the same key drives a size-k selection instead: heapq.nsmallest(k, counts, key=lambda v: (-counts[v], v)) returns the same answer in O(d log k).

Walk through an example

The first example, nums = [1, 1, 1, 2, 2, 3] and k = 2: one counting pass, one sort, one slice.

Complexity

Count, then sort: O(n + d log d) time for n numbers with d distinct values (one counting pass, one sort of the distinct values) and O(d) space for counts and ranked. A size-k heap makes the ranking O(d log k). Brute force: O(n · d) time, because each of the d counts rescans the whole list, and O(d) space.

Edge cases to test

• Ties that insertion order gets wrong: [5, 5, 4, 4, 6], k = 2 must give [4, 5]. A key on count alone returns [5, 4], because the dict keeps first-appearance order and the sort is stable.
• All values distinct: [9, 8, 7], k = 2 gives [7, 8]. Every count is 1, so the tie-break alone decides.
• k equal to the number of distinct values: [3, 1, 2, 2], k = 3 gives [2, 1, 3], every value still in rank order, with 1 before 3 on their tie.
• Negative values: [-1, -1, 0], k = 1 gives [-1]. A counting array indexed by value breaks here, and silently in Python, where index -1 is the last slot.
• A single element: [7], k = 1 gives [7]. A bucket array needs n + 1 slots, because a count can equal n.

Common mistakes

• Recounting with nums.count(v) inside the sort key: correct, but every call rescans the list, so it is O(n · d).
• Breaking ties by accident: a key on count alone returns [5, 4] for [5, 5, 4, 4, 6], k = 2, because Python’s sort is stable and the dict keeps first-appearance order.
• Using reverse=True on (count, value) to get counts descending: it flips the tie-break too, so ties come out larger value first.
• Sizing a bucket array as n instead of n + 1: a value can occur n times, so buckets[n] must exist.

Follow-ups an interviewer asks next

The input is a stream too large to store, with too many distinct values to count.

Exact top-k needs a counter per distinct value, so memory grows with d. When that is too much, approximate. Misra-Gries and Space-Saving keep a fixed number of counters, guarantee that every value above a frequency threshold of roughly n divided by the counter count survives, and bound the error of each count. A Count-Min sketch plus a size-k heap of candidates is the other common design.

Can you beat sorting the distinct values?

Yes. A size-k selection with the same key, heapq.nsmallest or a min-heap that pops whenever it holds more than k, costs O(d log k). Buckets indexed by count, which runs from 1 to n, read from the high end, cost O(n) when ties need no order; with this problem’s tie rule, each bucket you read must also be ordered, which can cost O(d log d) when most values share one count.

Return the top k words instead of numbers, ties in alphabetical order.

Same algorithm, different key: count the words, then sort by (-count, word), since Python compares strings lexicographically. In TypeScript, replace a - b with a string comparison, either a.localeCompare(b) or a plain a < b test. Those two disagree on mixed case and non-ASCII text, so choose one and test it.

The counts keep changing, like a live trending list.

Keep counts in a hash map and the ranking in an ordered structure keyed by (-count, value), such as a balanced tree or a sorted container. Each increment removes the old key and inserts the new one in O(log d), and the top k are the first k entries. For trends that should fade, count per time bucket and drop buckets as they expire.

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.

Reference solution

def top_k_frequent(nums, k):
    counts = {}
    for x in nums:
        counts[x] = counts.get(x, 0) + 1
    ranked = sorted(counts, key=lambda v: (-counts[v], v))
    return ranked[:k]


print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))   # -> [1, 2]

function topKFrequent(nums: number[], k: number): number[] {
  const counts = new Map<number, number>();
  for (const x of nums) counts.set(x, (counts.get(x) ?? 0) + 1);
  return [...counts.keys()]
    .sort((a, b) => (counts.get(b)! - counts.get(a)!) || a - b)
    .slice(0, k);
}

console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2));   // -> [1, 2]