Top K Elements

Size-K Heap · Quickselect · Bucket Sort

1:00

Find the K largest, smallest, or most-frequent values in O(n log k) using a size-K heap — without sorting the whole array.

By the end, you can

Explain why a full sort is wasteful for Top-K problems.
Identify which heap type (min or max) to use for K largest versus K smallest.
Trace the push-then-evict loop on a small example and state the final heap contents.
State the time and space complexity of the size-K heap approach and compare it to full sort.
Describe quickselect, state its average (O(n)) and worst-case (O(n²)) complexities, and explain how to mitigate the worst case (a randomized or median-of-medians pivot).
Choose bucket sort for the K-most-frequent variant and explain why it is O(n).
Avoid the three common pitfalls: wrong heap direction (use a min-heap to keep the top-k largest), assuming quickselect is always O(n), and re-sorting the whole array when only the top k are needed.

Up next in Coding Interview Patterns