Run it
All three approaches with the number of elements each one stores, then timed on a large array so the O(k) memory claim and the O(n) average are both visible.
The three answers, in order
Sort. O(n log n), one line, and the correct opening.
A min-heap of size k. O(n log k) time, O(k) space. Keep the k largest seen so far; the smallest of them sits at the root and is the answer at the end.
Or in one line with the standard library, which uses exactly this strategy: heapq.nlargest(k, nums)[-1].
Why a min-heap for the largest elements? This inversion confuses people. The heap holds the k best candidates, and the element to evict when a better one arrives is the worst of them — so the root must be the minimum. A max-heap would put the wrong element within reach.
When k is small, O(n log k) is close to linear: finding the top 10 of a million elements does about 20 million comparisons rather than sorting all of them.
Quickselect: expected O(n)
Partition like quicksort, then recurse into only the side containing the answer. Because one half is discarded each time, the expected work is n + n/2 + n/4 + … = O(n).
Expected O(n), worst case O(n²), O(1) extra space.
The random pivot is not optional. With a fixed pivot such as the last element, sorted input causes maximally unbalanced partitions and the algorithm degrades to O(n²) — on precisely the input someone is most likely to test with. Randomising makes that outcome vanishingly unlikely regardless of the input.
Two other caveats worth stating: quickselect mutates the input array, which may not be acceptable, and it needs the whole array in memory, so it cannot process a stream.
Three answers, and the reason to choose
Sort and index. sorted(a)[-k]. O(n log n), one line, and the right answer in real code for any array that fits in memory.
Min-heap of size k. O(n log k) time and O(k) memory. The only one that works on a stream, or when n is far larger than memory.
Quickselect. O(n) average by partitioning and recursing into one side only. O(n²) worst case with a bad pivot, fixable with a random one.
Interviewers are usually listening for whether you notice the heap is bounded by k rather than n.
Why a min-heap for the largest
It feels backwards and it is the key idea. To keep the k largest values you need constant-time access to the smallest of the ones you kept, because that is the one to evict when something better arrives. A min-heap puts exactly that at the root.
Once the heap is full, a value below the root cannot be in the top k, so it is discarded without being stored at all.
Quickselect, briefly
Partition around a pivot as quicksort does, then recurse into only the side containing position k. Because one side is discarded each time, the expected work is n + n/2 + n/4 + ... = O(n).
Its worst case is O(n²) on a bad pivot sequence, so pick the pivot at random. Say that explicitly — "quickselect, with a random pivot" is a complete answer, and "quickselect" alone invites the follow-up about sorted input.
Choosing between them
| Approach | Time | Space | Mutates | Streaming |
|---|
| Sort | O(n log n) | O(n) | No (with sorted) | No |
| Min-heap of size k | O(n log k) | O(k) | No | Yes |
| Quickselect | O(n) expected | O(1) | Yes | No |
| Counting sort | O(n + range) | O(range) | No | No |
| Median of medians | O(n) worst case | O(n) | Yes | No |
The decision usually comes down to three questions, and asking them is a better answer than picking one:
Is k small relative to n? Then the heap, at nearly linear time and tiny memory. Does the data fit in memory and can it be reordered? Then quickselect. Does the data arrive as a stream, or is n unknown? Then the heap — it is the only option that never needs the whole input.
Counting sort deserves a mention when the value range is small and known: bucket by value and walk down from the top. O(n) with no comparisons, and only viable for bounded integers.
Median of medians guarantees O(n) worst case by choosing a provably good pivot. The constant factor is large enough that it loses to randomised quickselect in practice, and knowing it exists is the point — it is why "linear-time selection" is a solved problem in theory.
The streaming variant
"Design a class that returns the k-th largest element as numbers are added" is the natural follow-up, and it is where the heap becomes clearly correct:
heapify is O(n) while n individual pushes are O(n log n) — a small detail that interviewers notice.
Each add is O(log k) and memory stays at O(k) no matter how many numbers arrive. Quickselect cannot do this at all, which is the cleanest illustration of why the "best" algorithm depends on the access pattern rather than on the asymptotic bound alone.
Top k frequent elements. Count with a Counter, then heap or quickselect on the counts. Counter.most_common(k) does it directly.
K closest points to the origin. Identical structure with distance as the key; a max-heap of size k this time, since the k smallest are wanted.
Median of a data stream. Two heaps — a max-heap for the lower half and a min-heap for the upper — kept balanced.
K-th smallest in a sorted matrix. Binary search on the value, counting elements below a candidate.
Merge k sorted lists. A heap of size k holding one element from each list.
The transferable idea: a bounded heap keeps the best k of an unbounded stream in O(k) memory. That is the pattern behind "top N" dashboards, leaderboards, and log analysis over data far larger than memory.
What it is testing
Do you offer more than sorting? Sorting is the right first answer and the wrong last one.
Do you understand why a min-heap finds the largest? The root must be the worst candidate, so it is the one evicted.
Do you randomise the quickselect pivot? Without it, sorted input is O(n²).
Do you ask about the constraints? Streaming, memory, and whether the input can be mutated each change the answer.
Do you know heapify is O(n)? Cheaper than pushing n times.
Do you clarify duplicates? K-th largest by position in sorted order, not k-th distinct value.
Recap in one screen
- Sorting is O(n log n) and the baseline to improve on.
- A min-heap of size k gives O(n log k) time and O(k) space, and works on a stream.
- Quickselect is O(n) expected with O(1) space, mutates the input, and needs a random pivot to avoid O(n²).
heapify an existing list in O(n) rather than pushing element by element.- Ask about streaming, memory and mutability — they determine which approach is right.