Top 'K' Elements: The Heap Pattern Explained

TL;DR: When a problem says "the k largest / smallest / most frequent / closest," you don't sort everything (O(n log n)); you keep a heap of size k (O(n log k)). The counterintuitive part that interviewers deliberately probe: to track the k largest elements you use a min-heap, because its root is the weakest member of the club, the one the next candidate must beat to get in. Learn that one inversion, the size-k template, and the quickselect follow-up, and the entire "k of something" family becomes mechanical.

This is the sixth deep dive in our pattern series, after sliding window, two pointers, fast & slow pointers, merge intervals, and monotonic stack. Top-K has the most honest tell in interviewing (the literal letter k in the problem statement) and one of the highest hit rates in real loops: Kth Largest, Top K Frequent, and K Closest Points are staples at Meta, Amazon, and Google screens alike. It's also the pattern where interviewers most reliably test understanding versus recitation, with one simple question: "why is that a min-heap?"

The tell: how to recognize a Top-K problem

• "find the k largest / k smallest elements"
• "the kth largest element" (just the one, but same machinery)
• "k most frequent words / elements"
• "k closest points to the origin / values to a target"
• "sort characters by frequency" (k = all of them, frequency is the key)

The tell is the selection: you need some of the extremes, not a full ordering. The moment you catch yourself writing sort() and taking a slice, ask whether the problem actually needs the other n minus k elements ordered. It almost never does, and that's exactly the waste this pattern deletes.

The inversion: why k-largest means min-heap

Here's the explanation to give in an interview, because the inversion is what's actually being probed.

Think of the heap as a club with k seats, and you're maintaining the k largest elements seen so far. The only decision you ever make is at the door: does the newcomer deserve a seat? To answer that, you compare the newcomer against the weakest current member, because that's who would lose their seat. A min-heap gives you the weakest member in O(1), right at the root. So: tracking the k largest requires instant access to the smallest of them, hence a min-heap. (And symmetrically, k smallest wants a max-heap.)

Candidates who memorized "use a heap" without the inversion build a max-heap of all n elements and pop k times. It works, but it's O(n) space and O(n + k log n) time, and it tells the interviewer you've memorized the prop, not the play.

The template

Kth Largest Element (LeetCode 215), the canonical form:

import heapq

def find_kth_largest(nums, k):
    heap = []                       # min-heap of the k largest so far
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x) # seats still free
        elif x > heap[0]:           # beats the weakest member?
            heapq.heapreplace(heap, x)  # evict root, admit x
    return heap[0]                  # the weakest of the k largest = kth largest

O(n log k) time, O(k) space, and the last line is a small gift: the root of a k-sized min-heap of the largest elements is the kth largest, no popping required. Say the complexity comparison out loud: for n = 1,000,000 and k = 10, log k is ~3 while log n is ~20, and the heap never holds more than 10 items. That's the pattern's entire value proposition in one sentence.

The variations, and what each one adds

• Top K Frequent Elements (LeetCode 347): count with a hash map first, then run the template on (frequency, element) pairs. The pattern composes with hashing, and this two-stage shape (aggregate, then select) is the most common disguise.
• K Closest Points to Origin (LeetCode 973): same template with distance as the key, and the inversion flips (k closest = k smallest = max-heap). If you can explain why the flip happens, you own the pattern.
• Kth Largest Element in a Stream (LeetCode 703): the template as a class: keep the size-k heap alive between calls. This is where the O(k) space bound stops being a nicety and becomes the whole point, because the stream is unbounded.
• Sort Characters by Frequency / Reorganize String: frequency counting plus a heap you pop from, greedily. Reorganize String adds the interview twist (never place the same char twice in a row), solved by holding the just-used element out of the heap for one turn.
• Merge k Sorted Lists (LeetCode 23): a heap of size k holding one head per list, pop the smallest, push its successor. Strictly speaking this is the K-way Merge pattern, Top-K's sibling, and it's next in this series.

Want every variation taught step by step? The Top-K chapter of Grokking the Coding Interview builds from Kth Largest through the streaming and frequency variants with visual heap traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The follow-up interviewers love: "can you beat O(n log k)?"

For the single kth element (not the full top k), yes: quickselect, the quicksort partition applied to only one side, runs O(n) on average. The trade-offs you should be able to state: quickselect is average-case O(n) but worst-case O(n²) (mitigated by random pivots), it needs the whole array in memory and mutates it, and it produces only the kth element, not a maintained set. So: streams and "give me all k" favor the heap; a one-shot kth on a mutable array favors quickselect. Knowing which tool when, and saying the trade-offs unprompted, is senior-signal, and this exact follow-up is a Meta and Amazon favorite.

The three mistakes that sink candidates

1. Heaping all n elements. The size-k constraint is the pattern. A heap of everything gives the right answer with the wrong complexity, and interviewers ask "what's your space usage?" precisely to catch it.

2. Fighting the language's heap direction. Python's heapq is min-only, so k-smallest problems need negated keys (heappush(heap, -x)), and forgetting to negate on the way out is the classic bug. Java's PriorityQueue is also min-first; C++'s priority_queue is max-first. Know your language's default before the interview, not during.

3. Unstable tuple comparisons. Pushing (freq, word) tuples works until two frequencies tie and the heap compares the second field, which either crashes (uncomparable objects) or silently applies an ordering you didn't choose (and Top K Frequent Words requires a specific tie-break). Push an explicit, fully-decided key. Ties are where heap solutions go to die in interviews.

Practice ladder

In order; each rung adds one wrinkle.

1. Kth Largest Element in a Stream (E): the template as persistent state.
2. Kth Largest Element in an Array (M): the canonical form; rehearse the min-heap inversion out loud.
3. Top K Frequent Elements (M): compose with a frequency map.
4. K Closest Points to Origin (M): the flipped inversion (max-heap).
5. Sort Characters by Frequency (M): pop-greedily instead of maintaining.
6. Reorganize String (M): the hold-one-out greedy twist.
7. Merge k Sorted Lists (H): the bridge into K-way Merge.
8. Stretch goal: Find K Pairs with Smallest Sums (M/H): the heap as a frontier over an implicit matrix, the pattern's hardest costume.

Then write the tell in your own words ("I should suspect Top-K when ___") and move on: recognition over volume, as always.

The takeaway

One tell (the literal k), one inversion (largest lives in a min-heap, because the root is the bouncer), one complexity story (n log k beats n log n because k is small), and one follow-up (quickselect, with trade-offs). The full pattern map lives in the complete guide, and next in the series is Top-K's sibling: K-way Merge, where the heap stops selecting winners and starts weaving sorted streams together.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79. Short on time? Grokking 75 covers the essential heap problems in its 6-week plan.

FAQs

Why use a min-heap to find the k largest elements? Because the only comparison that ever matters is against the weakest of your current top k, and a min-heap keeps exactly that element at its root in O(1). Newcomers either beat the root (evict it, enter) or don't (discard). A max-heap of everything also works but costs O(n) space instead of O(k).

What's the time complexity of the Top-K heap pattern? O(n log k): n elements each doing at most one push/replace on a heap that never exceeds k items. Against full sorting's O(n log n), the win grows as k shrinks relative to n, and for streaming data the O(k) memory bound is the difference between possible and impossible.

When should I use quickselect instead of a heap? One-shot kth element on an in-memory array you're allowed to mutate: quickselect averages O(n). Need the full top-k set, stable behavior, or streaming input: heap. In interviews, give the heap solution first, then offer quickselect as the optimization when asked; that ordering shows judgment.

How do I do a max-heap in Python? Negate the keys: push -x, and negate again when reading. heapq only implements a min-heap. Wrap the negation immediately in both directions; the sign-flip-on-exit is one of the most common heap bugs in interviews.

Is the Top-K pattern common in FAANG interviews? Very: Kth Largest and Top K Frequent are among the most-asked questions at Meta and Amazon, K Closest Points is an Amazon screen staple, and the quickselect follow-up is nearly scripted. It's high-frequency because it's quick to state, has clean escalations, and cleanly separates memorizers from pattern-owners with one "why min-heap?" question.