Top K Frequent Elements: Count, Then Choose Your Weapon

If you interview at Amazon, Meta, Uber, expect some version of "Top K Frequent Elements". It is rated Medium, and it falls squarely into the Top-K and Heaps pattern — pattern-first preparation beats grinding random problems every time. Part 4 of 11 in the Top-K and Heaps arc.

The Problem

Return the k most frequent elements of an array, any order. The two-stage shape — build a frequency map, then select the top k entries by count — underlies a whole family (frequent words, frequent IPs in logs) and is a system design conversation seed as much as a coding question.

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

Recognizing the Top-K and Heaps Pattern

When a problem asks for the k largest, smallest, closest, or most frequent — or for repeated access to an extreme while data changes — a heap gives O(log n) insertion and O(1) access to the extreme. The signature trick: keep a bounded heap of size k with the opposite polarity (a min-heap to track the k largest), evicting the root on overflow. Python's heapq is a min-heap; negate values for max behavior.

Top k by a derived score (frequency) is Top-K applied to a map's items. The bounded min-heap on (count, value) pairs gives O(n log k); frequencies being integers bounded by n also unlocks bucket sort at O(n) flat — a rare chance to beat the heap and name the reason (bounded key domain).

The Approach

Counter(nums) in O(n). Then maintain a size-k min-heap over (count, value): push each item, evict the root past k. Pull the survivors. heapq.nlargest(k, counter.keys(), key=counter.get) is the stdlib spelling of the same idea and is interview-legal if you can explain its internals.

Bucket variant: index lists of values by count (1..n), read buckets from the top until k collected. O(n) time, and the natural answer when the interviewer says 'can you do better than n log k?'

Python Solution

import heapq
from collections import Counter


def top_k_frequent(nums: list[int], k: int) -> list[int]:
    """K most frequent values, via a bounded min-heap over counts."""
    counts = Counter(nums)
    heap: list[tuple[int, int]] = []
    for value, count in counts.items():
        heapq.heappush(heap, (count, value))
        if len(heap) > k:
            heapq.heappop(heap)
    return [value for _, value in heap]

Complexity

• Time: O(n log k) — n counter updates plus distinct-element pushes into a k-bounded heap
• Space: O(n) — the frequency map dominates

Interview Tips and Follow-Ups

• The problem usually guarantees a unique answer set — if ties were possible, define tie-breaking before the interviewer does.
• Top K Frequent Words adds lexicographic tie-breaks — the heap needs (−count, word) with careful ordering; a classic Amazon variant.
• At data-engineering scale, exact counts stop fitting in memory — Count-Min Sketch plus a heap is the streaming answer; one sentence of it impresses.

That wraps part 4 of the Top-K and Heaps arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.