Algorithm

Top K Frequent Elements

Heaps & Priority Queues Pattern

Top K Frequent Elements

Given an integer array nums and an integer k, return the k elements that appear most often.

Return the element values themselves, not their counts. The output may be in any order. The input guarantees the answer is unique — there is never a tie straddling the kth position that would make two different answers equally valid.

CONSTRAINTS
  • 1 <= nums.length <= 10⁵
  • -10⁴ <= nums[i] <= 10⁴
  • k is in the range [1, number of distinct values in nums]
  • The answer is guaranteed to be unique.
  • Follow-up: your algorithm must run in better than O(N log N) time.
EXAMPLE 1
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1 occurs three times, 2 occurs twice, 3 occurs once. The two highest counts belong to 1 and 2. Note the output holds the values, not the counts 3 and 2.
EXAMPLE 2
Input: nums = [4,1,-1,2,-1,2,3], k = 2
Output: [-1,2]
Both -1 and 2 occur twice; 4, 1 and 3 occur once each. Negative values are ordinary elements here — only how often a value appears matters, never how big it is.
EXAMPLE 3
Input: nums = [7,7,8,9], k = 3
Output: [7,8,9]
There are exactly three distinct values, and k equals that count, so every distinct value makes the cut regardless of its frequency. Repeats collapse: 7 appears twice in the input but only once in the output.
EXAMPLE 4
Input: nums = [5], k = 1
Output: [5]
One element, one distinct value, and it trivially has the highest count.
What should happen if two elements are tied at the kth position?
The statement guarantees that cannot occur, so any single valid output is accepted. Worth asking anyway — if the guarantee were dropped you would need a stated tie-break rule (smallest value first, first-seen first), and the choice changes the code.
Does the order of the returned elements matter?
No. Any ordering of the correct k elements is accepted. That matters more than it sounds: it means you never have to sort the winners among themselves, which removes work from the final step.
Do you want the values or their frequencies?
The values. The counts are only the ranking key used along the way.
How large can the value range be? Are they bounded small integers?
Here they lie in [-10⁴, 10⁴], but do not build the solution around that. The number of distinct values can still reach 10⁵ in a general version of this problem, and the fastest approach depends on the range of the *counts*, not of the values themselves.

Two separate questions live inside this one statement, and separating them is most of the work. First: how often does each value occur? Second: given those counts, which k values have the highest ones? The first question has one sensible answer. The second is the interesting part, and it is a problem we have already solved once.

Step one: counting, and why a hash map is the right tool

To know that 1 appears three times you must visit every element, so no counting method beats one full pass. The only decision is where the running tallies live. A hash map stores key-to-value pairs and finds any key in roughly constant time — it converts the key into an array position by running it through a hash function, so a lookup is arithmetic followed by one memory access, not a search. That gives us the counts in O(N):

python
from collections import Counter
counts = Counter(nums)      # {1: 3, 2: 2, 3: 1}

Call the number of distinct values M. Note M can be much smaller than N — that is the whole point of counting, it shrinks the problem — but in the worst case, all elements distinct, M equals N.

Step two, naively: sort the counts
python
def top_k_frequent(nums, k):
    counts = Counter(nums)
    ordered = sorted(counts, key=counts.get, reverse=True)   # O(M log M)
    return ordered[:k]

Correct, short, and it is what most people write first. The cost is O(N + M log M), which is O(N log N) when values are mostly distinct. And the waste is precisely the one named in Kth Largest: sorting decides the relative rank of every pair of distinct values, including the ranks of everything below the cutoff, when the question only cares which k are on top and does not even care about the order among those. The follow-up explicitly asks for better than O(N log N), so this approach is what the interviewer wants you to improve on.

The same shortlist, keyed differently

Everything from Kth Largest transfers directly. Walk the (value, count) pairs, keep a shortlist of the k with the highest counts in a min-heap, and evict the weakest whenever the shortlist overflows. Filling the three slots of that pattern:

- The key is the count, not the value. This is the only real change — the heap must compare pairs by their first component, so push tuples of (count, value).
- The direction stays min-heap, because we want the top k and therefore always evict the lowest count.
- The read changes: last time we returned the root alone, here we return every value left in the heap. Since output order is free, no sorting of the winners is needed.
python
import heapq
from collections import Counter

def top_k_frequent(nums, k):
    counts = Counter(nums)
    shortlist = []
    for value, count in counts.items():
        heapq.heappush(shortlist, (count, value))   # ordered by count first
        if len(shortlist) > k:
            heapq.heappop(shortlist)                # drop the least frequent
    return [value for count, value in shortlist]

The heap holds at most k entries and each of the M pairs causes at most one push and one pop, so this is O(N + M log k) time and O(M) space — the map dominates the memory. Better than sorting whenever k is meaningfully smaller than M, which is the case the problem is built around.

Crucial Notethe heap is iterated over exactly once, at the very end, and its internal array order is not sorted by count. The heap property only guarantees that the root is the minimum; siblings are unordered. If a variant of this problem asked for the k elements listed from most to least frequent, you would have to pop them one at a time — that yields them in ascending order, so you would then reverse the result. Reading the heap's backing array and assuming it is sorted is a genuinely common bug.
Doing better than log: counting instead of comparing

O(N + M log k) still has a log in it. Getting rid of it needs an observation about the counts themselves, not the values. A count is a number of occurrences, so it is a whole number between 1 and N. There are only N possible counts, and they are small integers with no gaps in their range.

Whenever ranking keys are small bounded integers, you can stop comparing and start indexing. Build an array of N+1 empty lists, and place each value into the slot matching its count: everything appearing exactly 3 times goes into slot 3. Now the ranking is not computed at all — it is the geometry of the array. Sweep from the highest slot downward, collecting values until you have k of them.

python
def top_k_frequent(nums, k):
    counts = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]   # index = frequency
    for value, count in counts.items():
        buckets[count].append(value)

    result = []
    for count in range(len(nums), 0, -1):          # highest frequency first
        for value in buckets[count]:
            result.append(value)
            if len(result) == k:
                return result
    return result

Every phase is linear: counting is O(N), filling buckets is O(M), and the downward sweep touches N+1 slots and at most M values. Total O(N) time and O(N) space. This is the answer the follow-up is fishing for.

The trade is real, though, and you should state it: the bucket array is sized by N regardless of how few distinct values exist, so for an array of a million elements with three distinct values it allocates a million mostly-empty slots. The heap version's memory scales with the data that actually exists. Bucketing beats comparison only because the key range is known and small — remove that guarantee and the technique collapses.

Worked example:nums = [4,1,-1,2,-1,2,3], k = 2

Counting first: 4 appears once, 1 once, -1 twice, 2 twice, 3 once. So the map is {4:1, 1:1, -1:2, 2:2, 3:1}.

Following the heap version, processing pairs in map order:

- (1, 4) pushed. Shortlist holds one entry, under capacity.
- (1, 1) pushed. Two entries, at capacity.
- (2, -1) pushed, three entries, so evict the smallest count. Both existing entries have count 1; the tuple comparison breaks the tie on the value, so (1, 1) leaves. Shortlist: (1, 4) and (2, -1).
- (2, 2) pushed, evict the smallest — (1, 4), count 1. Shortlist: (2, -1) and (2, 2).
- (1, 3) pushed, evict the smallest. The new entry itself has the lowest count, so it leaves immediately. Shortlist unchanged.

Strip the counts off the two survivors: [-1, 2]. Both really do occur twice while everything else occurs once, and since order is free, [2, -1] would be equally correct.

Now the bucket version on the same input. Slot 1 collects [4, 1, 3] and slot 2 collects [-1, 2]; every other slot is empty. Sweep downward from slot 7: empty, empty, …, slot 2 yields -1 and then 2, and with two values collected we stop. Same answer, and notice we never looked at slot 1 at all — the elements that lose are never examined.

The takeaway

The heap did not change between this problem and Kth Largest; only what it ranks by changed. That is the payoff of learning a pattern as a skeleton with slots — the second problem in a family should feel like filling in a form, and the effort moves to deciding what the ranking key is.

The deeper lesson is the third approach. Heaps are comparison-based, and comparison-based selection has a log in it that cannot be removed. The moment your ranking key is a small bounded integer — a frequency, a score out of 100, an age in years, a character code — you can index instead of compare and drop the log entirely. Train that reflex: after you have a working heap solution, always ask what is the range of my key? If the answer is "small and bounded", there is a faster solution and the interviewer is probably waiting for it.

O(N log N) Sort By Count
→
O(N + M log K) Bounded Min-Heap
→
O(N) Frequency Buckets