LeetCode 347 · Arrays & Hashing

Top K Frequent Elements, explained with a picture

The k most frequent visitors.

MediumArrays & Hashing
▶ Watch it step by step

The problem

Given a list of numbers and a number k, return the k numbers that appear most often.

Input:  nums = [1,1,1,2,2,3,4,4,4,4], k = 2
Output: [4, 1]   (4 appears 4 times, 1 appears 3 times)

Picture it

Imagine a clinic logbook full of visitor IDs. First we count how many times each visitor came. Then we line the visitors up in buckets by visit count: bucket 1 holds people who came once, bucket 2 those who came twice, and so on. Reading the buckets from the highest count down, the first k visitors we meet are the answer.

How to recognise it

  • The question asks for the top k of something (the k largest, most frequent, closest).
  • You need the k winners, not a full ranking of everything.
  • The score here is a frequency, so you must count first with a dictionary.
  • Up to 10^5 numbers. LeetCode's follow-up asks for better than O(n log n), which hints that sorting everything is more than needed.

Start with brute force

For each distinct value, count how often it appears by scanning the list, then sort the values by count and take the first k.

def top_k_brute(nums, k):
    freq = {v: nums.count(v) for v in set(nums)}   # each count scans the list
    order = sorted(freq, key=lambda v: freq[v], reverse=True)
    return order[:k]

With d distinct values, the counting alone is O(n · d), up to O(n²). If all 10^5 numbers differ, that is 10^10 steps. Sorting adds O(d log d). Space is O(d).

Counting in one pass with a Counter fixes the first part at O(n). Sorting all d values by count then costs O(d log d), which works, but does more than the problem needs.

From brute force to the idea

  1. Count once. Counter(nums) builds value → count in one O(n) pass.
  2. Find the waste. Sorting puts all d values in order, but only the top k matter. The order of the rest is wasted work.
  3. Keep a small shortlist. Hold at most k (count, value) pairs in a min-heap: a structure that keeps the smallest item on top and can add or remove in O(log size).
  4. Push, then trim. Push each pair. If the heap now has k + 1 items, pop the top, which is the least frequent of them. The k most frequent seen so far always survive.
  5. Read the answer. After every value has been offered, the heap holds exactly the k most frequent values.

This is the key idea: a min-heap capped at size k, whose top is the weakest member and the first to be dropped.

The key idea

Count with a dictionary, then use “bucket by count”: no full sort needed, so it runs in O(n).

Python solution

def top_k_frequent(nums, k):
    count = Counter(nums)
    heap = []                     # (visits, value), fewest on top
    for x, c in count.items():
        heappush(heap, (c, x))
        if len(heap) > k:
            heappop(heap)
    return [x for c, x in heap]

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import Counter from heapq import heappush, heappop

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n · d + d log d): one scan of the list per distinct valueO(d): the count table
Counter + size-k heap (shown code)O(n + d log k): one counting pass, then each push or pop is O(log k)O(d + k): the Counter and the heap

Edge cases

  • k equals the number of distinct values: nothing is ever popped, so every value is returned.
  • Single number ([1], k = 1): returns [1].
  • Output order: the result is in heap order, not sorted by frequency. For the example it returns [1, 4], not [4, 1]. LeetCode accepts any order; sort the result if a caller needs it ranked.
  • Ties at the cut-off: LeetCode promises a unique answer. If two values did tie, the pair (count, value) compares by value next, so the smaller value is popped first.
  • Negative numbers: work unchanged, since the value is only a tie-breaker.
  • Missing imports: the code needs from collections import Counter and from heapq import heappush, heappop; without them it raises NameError.

Common mistakes

  • Using a max-heap (or negated counts) but still popping when the size passes k. That throws away the most frequent values and keeps the least frequent.
  • Pushing all d values into a heap and popping k times. Still correct, but O(d + k log d) with O(d) heap space, so it no longer benefits from small k.
  • Forgetting the heap stores pairs and returning them as-is instead of extracting the values.

An O(n) alternative is bucket sort: make a list of buckets indexed by count (0 to n) and read them from the highest down.

Your turn: top k frequent words

Given a list of words and k, return the k most frequent words, sorted by frequency from high to low, with ties broken alphabetically. For ["i", "love", "leetcode", "i", "love", "coding"] and k = 2 the answer is ["i", "love"]. Describe your approach, then write it if you like.

Compare with our answer

Count with a Counter, then order the distinct words by the key (−count, word): the minus sign puts higher counts first, and equal counts fall back to alphabetical order.

from collections import Counter

def top_k_words(words, k):
    count = Counter(words)
    return sorted(count, key=lambda w: (-count[w], w))[:k]

Time O(n + d log d), space O(d). A size-k heap also works, but its comparison must be reversed for the words, which is easy to get wrong.

A strong answer mentions: a two-part sort key, negating the count rather than the word, and that the result here must be ranked, unlike in the original problem.

Check what stuck

1. Numbers arrive one at a time and you must always be able to report the 10 largest seen so far. Which approach fits best?

2. Why is each heap operation in the shown code O(log k) and not O(log d)?

3. A learner changes the push to heappush(heap, (-c, x)) and keeps everything else. What does top_k_frequent([1, 1, 1, 2, 2, 3], 2) return?

Score 60% or more and the lesson is marked complete.