Top-K, Heaps, Quickselect, And Frequency Analysis

What's being tested

Top-K selection tests whether you can avoid unnecessary full sorting when only a small subset or order statistic is needed. Interviewers probe your command of heaps, quickselect, frequency maps, and complexity tradeoffs under constraints like duplicates, ties, and large n.

Patterns & templates

• K closest points — compare squared distance x*x + y*y; use full sort O(n log n), max-heap O(n log k), or quickselect average O(n).

• K-th largest element — convert to index n - k in sorted ascending order; implement quickselect(nums, left, right, target) carefully.

• Min-heap for K largest — push elements, pop when size exceeds k; final heap contains answer set in O(n log k) time.

• Max-heap for K smallest / closest — store negative priority or custom comparator; cap heap size at k to avoid O(n) heap growth.

• Frequency analysis — build Counter / hashmap in O(n), then select top k by heap, bucket sort, or quickselect over unique keys.

• Bucket sort for frequencies — array of n + 1 buckets gives O(n) time for top frequent elements; space is O(n).

• Quickselect partitioning — average O(n), worst-case O(n^2); randomize pivot and be precise about <, >, and equal values.

Common pitfalls

Pitfall: Sorting everything by default is correct but may miss the expected optimization when the interviewer asks for O(n) or O(n log k).

Pitfall: For K-th largest, confusing k with zero-based index causes off-by-one errors; use target = len(nums) - k.

Pitfall: Returning heap contents without considering order is usually fine for “top K elements,” but not for “sorted top K”; clarify output requirements.

Practice these

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