Top-K Selection And Order Statistics

What's being tested

These problems test order statistics and top-K selection: finding the smallest, largest, median, or highest-ranked items without fully sorting everything. Interviewers expect you to choose between heap, quickselect, two-pointer, Trie augmentation, or streaming median based on input size, update pattern, and ordering rules.

Patterns & templates

• Min-heap frontier expansion for sorted combinations — push (sum, i, j), pop K times; typical O(k log k) with visited-pair deduping.

• Fixed-size max/min heap for top-K — maintain K best items in O(n log k) time; define comparator carefully for ties.

• Quickselect for unordered arrays — average O(n) time, worst O(n^2) unless randomized; returns partitioned top-K, not sorted top-K.

• Two-heaps streaming median — max-heap lower half, min-heap upper half; rebalance sizes so median query is O(1), insert O(log n).

• Augmented Trie top-K — store per-node top suggestions or frequency maps; prefix lookup is O(len(prefix)), but updates may cost O(len(word) * log k).

• Multi-key ranking comparator — order by frequency, distance, timestamp, lexicographic key; make comparator transitive and match required ascending/descending semantics.

• Approximate quantiles under memory limits — use bucket histograms, reservoir sampling, or sketches when exact median storage is impossible.

Common pitfalls

Pitfall: Fully sorting n items for every query gives O(n log n) when O(n log k), O(k log n), or cached metadata is expected.

Pitfall: Ignoring duplicate states in k-smallest-pairs can push (i, j) through multiple paths and inflate runtime or output duplicates.

Pitfall: Treating median as a batch problem when the interviewer asks for streaming updates misses the required online data-structure invariant.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.