Micro-questions over the top-k pattern. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.


A. Why it exists

1. Top 10 from a million items — what does sorting cost?

Answer

time and space — and you only need 10 of the million.

2. State the better idea.

Answer

Maintain a collection of the 10 largest seen so far. If a new item beats the smallest in the collection, replace it. time, space.

3. Define the pattern.

Answer

Find the largest (or smallest) elements without fully sorting. A heap is the tool that makes this cheaper than sorting everything just to look at the top of it.


B. The counterintuitive part

4. To find the largest, which heap do you use?

Answer

A min-heap of size .

5. Why is that the right way round?

Answer

The root is the smallest of your current top- — so it is exactly the thing to compare against and evict. If a new element beats the root, it is bigger than the current worst of your top-.

6. To find the smallest?

Answer

A max-heap of size — mirror image. In Python, negate on the way in and out.

7. Write the loop.

Answer
heap = []
for num in nums:
    heapq.heappush(heap, num)
    if len(heap) > k:
        heapq.heappop(heap)
return heap[0]        # k-th largest

8. Trace [3,2,1,5,6,4], .

Answer

[3] → [2,3] → push 1, pop 1 → [2,3] → push 5, pop 2 → [3,5] → push 6, pop 3 → [5,6] → push 4, pop 4 → [5,6]. Root = 5, the 2nd largest.

9. What does the root hold at the end?

Answer

The -th largest element overall, and the heap holds the top (in no particular order).


C. Costs

10. Why is it rather than ?

Answer

insertions and removals, each because the heap never grows past size .

11. When does it beat sorting?

Answer

Whenever is meaningfully smaller than .

12. When does sorting win instead?

Answer

When is close to — sorting has better cache locality and lower constant overhead.


D. Extensions

13. What is quickselect, and what does it cost?

Answer

A quicksort-style partition that recurses into only the side containing the -th element. Expected .

14. Why only one side?

Answer

After partitioning, the pivot is in its final position — so you know which side the -th element is on and can discard the other entirely.

15. What is quickselect’s worst case, and what fixes it?

Answer

with bad pivots. Median of medians — take medians of groups of 5, recursively find the median of those, and use it as pivot — guarantees worst case.

16. Quickselect is and the heap is . Why use the heap?

Answer

Quickselect mutates the array and needs it all in memory; the heap is a single streaming pass with space, so it works on data that never fits at once.

17. What does k-most-frequent need in addition?

Answer

A hash map to count occurrences first, then the heap over the (count, item) pairs.

18. Summarise the pattern in one sentence.

Answer

Keep a size- heap ordered the opposite way to what you are looking for, so the root is always the weakest member and the thing to evict.


Scorecard

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to LeetCode Patterns — University-Style Teaching Notes