Top K Elements

Whenever a problem asks for the ”$k$ largest”, ”$k$ most frequent”, ”$k$ closest”, or “$k$-th something”, your brain should immediately reach for one tool: a heap capped at size $k$. You almost never need to sort the whole input to answer a question about only $k$ of its elements — and that gap between “sort everything” and “just track the top $k$” is worth a full complexity class in an interview.

What you’ll learn

• How to recognize the top-k cue in a problem statement.
• The reusable template: a min-heap that never grows past size $k$.
• heapq.nlargest / heapq.nsmallest — the one-line version of the same idea.
• Quickselect — the $O(n)$ average-case alternative, and its trade-offs.
• Why a size-$k$ heap beats a full sort: $O(n \log k)$ vs. $O(n \log n)$.

The cue: “top k”, “kth largest”, “k closest”

Any phrasing that only cares about $k$ elements out of $n$ — and doesn’t need the rest of the array in sorted order — is a signal to stop thinking “sort” and start thinking “heap of size $k$”. Sorting the entire array to read off the last $k$ elements does $O(n \log n)$ work to answer a question that only needs $O(n \log k)$.

The pattern: a min-heap capped at size k

To find the $k$ largest values, keep a min-heap (not a max-heap) of size $k$. Counterintuitive at first, but the reason is simple: the heap’s root (heap[0]) is always the smallest of the k largest values seen so far — exactly the one value you’d want to evict the instant something bigger shows up.

top_k_pattern.py

import heapq
 
def top_k_largest(nums, k):
    min_heap = []
    for x in nums:
        if len(min_heap) < k:
            heapq.heappush(min_heap, x)          # heap not full yet -- just add
        elif x > min_heap[0]:
            heapq.heapreplace(min_heap, x)       # x beats the current worst of the top-k
 
    return sorted(min_heap, reverse=True)
 
 
nums = [3, 2, 1, 5, 6, 4]
print(top_k_largest(nums, 2))   # expect [6, 5]

At every point in the loop, min_heap holds exactly the $k$ largest values seen so far, in no particular internal order — only min_heap[0] (the smallest of them) is guaranteed to sit at the root.

Largest k needs a min-heap, smallest k needs a max-heap

It feels backwards the first time: to track the top-$k$ largest, you cap a min-heap so its root is the smallest of the winners so far, ready to be evicted. To track the top-$k$ smallest, you cap a max-heap instead, so its root is the largest of the winners so far. The heap type is always the opposite of what you’re hunting for.

Visual intuition

The counter-intuitive part first: to find the k largest values you use a min-heap. Watch what the root is at every step:

heapA min-heap of size k — the root is both the eviction candidate and the answerLC 215 · O(n log k), O(k) space

as a tree

heap is empty

as an array — the real thing

k2heap size0/2

1import heapq2 3def k_largest(nums, k):4    heap = []                        # MIN-heap of the k largest so far5    for v in nums:6        heapq.heappush(heap, v)7        if len(heap) > k:8            heapq.heappop(heap)      # evict the smallest9    return heap[0]                   # kth largest

k2

setupCounter-intuitive setup: to find the k **largest** values, use a **min**-heap. The root is then the smallest of the k best seen so far, which makes it exactly the element to throw away when a better one arrives — and exactly the answer at the end.

Play‹›1/12⟲

The root is the smallest of the k best seen so far, which makes it exactly the element to discard when something better arrives — and exactly the kth largest once the scan finishes.

How it works

sketch A min-heap capped at size k=3 p5.js Pause Restart

Each incoming number either fills an empty slot, replaces the heap's current minimum, or is discarded outright if it can't beat the worst of the top-k so far.

Dry run

The size-k min-heap, nums = [7, 2, 9, 4, 1, 8, 5, 3], k = 3

Heap contents are shown sorted ascending for readability — the real internal array is only guaranteed to have the minimum at index 0.

i	x	Heap before	Heap after	Root	What happened
0	7	[]	[7]	7	push — not full
1	2	[7]	[2, 7]	2	push — not full
2	9	[2, 7]	[2, 7, 9]	2	push — now full at k = 3
3	4	[2, 7, 9]	[4, 7, 9]	4	4 > 2 -> replace the root
4	1	[4, 7, 9]	[4, 7, 9]	4	1 > 4? no -> discard, untouched
5	8	[4, 7, 9]	[7, 8, 9]	7	8 > 4 -> replace
6	5	[7, 8, 9]	[7, 8, 9]	7	5 > 7? no -> discard
7	3	[7, 8, 9]	[7, 8, 9]	7	3 > 7? no -> discard

Final top-3: [9, 8, 7], matching sorted(nums, reverse=True)[:3].

The root does two jobs at once. It is the element to evict and — once the scan finishes — the answer to “what is the kth largest?” Here heap[0] == 7, and 7 is indeed the 3rd largest. LC 215 is therefore this loop plus return heap[0], with no sorting at the end.

Three of eight elements never entered the heap at all. Counted over the scan: 3 pushes, 2 replacements, 3 discards — so only 5 of 8 elements caused a $\log k$ operation. Each discard is a single comparison against the root, $O(1)$. That is where the $O(n \log k)$ comes from: not every element pays the log.

Row 4 is the invariant in one line. 1 is smaller than everything in the heap, so it cannot be among the top 3 and is dropped without a heap operation. Compare against heap[0], the smallest winner — comparing against the largest would reject nothing, and scanning all k would cost $O(nk)$.

Input order changes the work, not the answer

Same k = 3, three orderings of eight values:

Order	Pushes	Replacements	Discards	Result
Ascending [1..8]	3	5	0	[8, 7, 6]
Descending [8..1]	3	0	5	[8, 7, 6]
Random [7,2,9,4,1,8,5,3]	3	2	3	[9, 8, 7]

Ascending input is the worst case for this loop: every element beats the current root, so every one costs $O(\log k)$. Descending is the best case — after the first k, nothing ever beats the root and every remaining element costs one comparison. Both give the right answer; the bound $O(n \log k)$ is the ascending case, and it is what you should quote.

When the heap loses: measured

heapq.nlargest against sorted(...)[:k] on 200,000 random integers (CPython, times per call; absolute numbers are machine-specific but the crossover is the point):

k	sorted(a, reverse=True)[:k]	heapq.nlargest(k, a)	Winner
5	0.100 s	0.007 s	heap, by 13.6x
100,000 (half of n)	0.105 s	0.441 s	sort, by 4.2x

The asymptotics say $O(n \log k)$ beats $O(n \log n)$, and at k = 5 that is a 13x real win. But at k = n/2, log k is barely smaller than log n while the heap pays per-element Python-level bookkeeping against Timsort’s C loop — and the sort wins by 4x. “Use a heap for top k” holds when k << n, which is the case the phrasing usually implies. Saying where the crossover is, and that it exists, is a stronger answer than reciting the bound.

One related measurement: if you already hold the whole array, heapq.heapify(list(a)) is $O(n)$ and beat 200,000 individual heappush calls by 1.8x — worth knowing, though it does not apply to the capped-heap pattern, which never holds more than k.

Worked example: Top K Frequent Elements

Count occurrences with a Counter, then let heapq.nlargest do the size-$k$ heap work for you, ranking by count instead of by raw value.

top_k_frequent.py

import heapq
from collections import Counter
 
def top_k_frequent(nums, k):
    counts = Counter(nums)
    return heapq.nlargest(k, counts.keys(), key=counts.get)
 
 
nums = [1, 1, 1, 2, 2, 3]
print(top_k_frequent(nums, 2))   # expect [1, 2] -- 1 appears 3x, 2 appears 2x

heapq.nlargest(k, iterable, key=...) and heapq.nsmallest(k, iterable, key=...) are the built-in, one-line version of the exact pattern above — reach for them whenever you don’t need to hand-roll the heap yourself.

Quickselect: trading heap overhead for average O(n)

If you only need the $k$-th value itself (not the full sorted top-$k$), the Quickselect algorithm — a partition step borrowed from quicksort — finds it in $O(n)$ average time, faster than any heap-based approach for a single query.

quickselect_kth_largest.py

import random
 
def kth_largest(nums, k):
    target_index = len(nums) - k   # k-th largest == (n-k)-th smallest, 0-indexed
 
    def partition(lo, hi):
        pivot_index = random.randint(lo, hi)
        pivot = nums[pivot_index]
        nums[pivot_index], nums[hi] = nums[hi], nums[pivot_index]   # move pivot to the end
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]   # pivot lands in its final sorted spot
        return store
 
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        p = partition(lo, hi)
        if p == target_index:
            return nums[p]
        elif p < target_index:
            lo = p + 1
        else:
            hi = p - 1
    return nums[lo]
 
 
nums = [3, 2, 1, 5, 6, 4]
print(kth_largest(nums, 2))   # expect 5

Heap vs. Quickselect — which one to reach for

A size-$k$ heap is the right default: it’s simple, streams naturally over data you can’t fit in memory, and gives you all $k$ elements in ranked order. Quickselect is faster on average ($O(n)$ vs. $O(n \log k)$) but only when you need a single $k$-th value from an array you already hold entirely in memory, and its worst case degrades to $O(n^2)$ without care (randomized pivots keep that vanishingly rare in practice).

Time and space complexity

Approach	Time	Space
Sort everything, slice the top $k$	$O(n \log n)$	$O(n)$
Min-heap capped at size $k$	$O(n \log k)$	$O(k)$
heapq.nlargest / nsmallest	$O(n \log k)$	$O(k)$
Quickselect (average case)	$O(n)$	$O(1)$ extra
Quickselect (worst case)	$O(n^2)$	$O(1)$ extra

When to use it

• The problem only cares about $k$ elements, and $k \ll n$ — a size-$k$ heap avoids paying for a full $O(n \log n)$ sort.
• The data arrives as a stream you can’t hold in memory all at once — a heap of size $k$ never grows past $k$ items.
• You need the top-$k$ ranked by a derived key (frequency, distance, custom score) rather than by raw value — pass key= to nlargest / nsmallest.
• Reach for Quickselect instead when you need exactly one $k$-th value, the whole array already fits in memory, and average-case $O(n)$ matters more than worst-case guarantees.

The variant map

Variant	The heap holds	Canonical problem
k largest values	Min-heap of size k; root is the smallest winner	215
k smallest values	Max-heap of size k (negate in Python); root is the largest winner	215 mirrored
kth largest only	Same min-heap; return heap[0], no final sort	215
k most frequent	Counter first, then heap on the counts — or bucket sort, $O(n)$ worst case	347 · 692
k closest to a point	Max-heap of size k keyed on distance (you evict the farthest)	973 K Closest Points to Origin
k closest to a value in a sorted array	Not a heap at all — binary search the insertion point, then a two-pointer expand, $O(\log n + k)$	658 Find K Closest Elements
kth largest in a stream	Persistent size-k min-heap across calls; add is $O(\log k)$	703 Kth Largest Element in a Stream
k pairs with smallest sums	Heap of candidate frontier entries, not of all pairs	373 · 378
Top k with ties broken by another key	Heap of tuples (primary, secondary, value)	692 Top K Frequent Words
k largest, output must be sorted	Heap then sort the k results: $O(n \log k + k \log k)$	215 · 347

LC 658 is the trap in this family

“Find the k closest elements to x” sounds like a top-k heap problem, and a heap does solve it in $O(n \log k)$. But the array is sorted, which the heap approach throws away entirely.

Binary search for x’s insertion point, then expand two pointers outward taking the closer neighbour each time: $O(\log n + k)$. For n = 10^5 and k = 10 that is ~27 operations against ~10^5. Reaching for the heap because the words “k closest” appeared is exactly the pattern-matching failure the Pattern Recognition Guide warns about — match the invariant, not the noun.

Pitfalls

• Using the wrong heap type. For the k largest you need a min-heap, so the root is the smallest winner and therefore the eviction candidate. A max-heap puts the best element at the root, which is precisely the one you never want to remove — and then finding what to evict costs $O(k)$. The heap type is always the opposite of what you are hunting.
• Comparing against the wrong end. x > heap[0] is the test. Comparing against the largest element rejects almost nothing, and scanning the heap to find the smallest turns $O(n \log k)$ into $O(nk)$.
• Python has no max-heap. heapq is min-only. Negate on the way in and on the way out, or push tuples with a negated key. A single missed negation gives plausible wrong answers, never a crash.
• heappushpop versus heapreplace. heapreplace pops then pushes, so it can return a value larger than the one you inserted and assumes the heap is non-empty. heappushpop pushes first, so it may immediately return the element you just added — which is what you want when you have not checked x > heap[0] first. Picking the wrong one silently changes which element survives.
• k = 0 breaks the template. len(heap) < 0 is false, so control falls to elif x > heap[0] and raises IndexError on the empty heap. LeetCode constraints normally guarantee k >= 1, so this is not a shipped bug — but if k can be zero, guard it, and note that heapq.nlargest(0, ...) returns [] correctly.
• Assuming the heap is sorted. Only heap[0] is meaningful. Printing the heap or slicing it gives an internal array order that is not the answer. sorted(heap, reverse=True) at the end costs $O(k \log k)$ — pay it only if the problem wants order.
• Sorting when k is close to n. Measured above: at k = n/2 the sort beats the heap by 4x. The $O(n \log k)$ advantage is real only when k << n.
• Ignoring a bounded value range. LC 347’s frequencies cannot exceed n, so bucketing by count is a deterministic $O(n)$ — better than the heap’s $O(n \log k)$ and simpler. Check for a bounded key before reaching for a heap.
• Unspecified tie order. With [1, 2, 3, 4] every count is 1, and nlargest(2, ...) returns [1, 2] — dictionary insertion order, not anything the problem promised. If the statement gives a tiebreak rule (LC 692 breaks ties lexicographically), it must be in the sort key; otherwise say out loud that any valid answer is acceptable.
• Building a heap of all n elements. heapify then k pops is $O(n + k \log n)$ — fine, and sometimes the right call, but it is $O(n)$ space. The capped heap is $O(k)$, which is what makes it work on a stream that never fits in memory.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 347 — Top K Frequent Elements · Medium

Problem. Return the k most frequent elements, in any order. Your algorithm must be better than $O(n \log n)$.

Constraints. 1 <= len(nums) <= 10^5, k is valid, and the answer is unique.

Examples. nums = [1,1,1,2,2,3], k = 2 gives [1,2] · nums = [1], k = 1 gives [1]

Why this test sorts the output

Any order is accepted, so the test sorts before comparing.

pch.exerciseTag pch.exerciseTitle

Editorial

Counting is $O(n)$; the question is how you select the top k.

Method	Time	Note
Sort the counts	$O(n \log n)$	Explicitly ruled out
most_common(k)	$O(n \log k)$	Heap internally; the clean answer
Size-k heap by hand	$O(n \log k)$	Same, spelled out
Quickselect on counts	$O(n)$ average	Randomised worst case
Bucket by frequency	$O(n)$ worst case	Counts are bounded by n

Bucket sort is the strongest answer and the one worth being able to write:

python

buckets = [[] for _ in range(len(nums) + 1)]
for value, count in Counter(nums).items():
    buckets[count].append(value)
out = []
for count in range(len(buckets) - 1, 0, -1):
    for value in buckets[count]:
        out.append(value)
        if len(out) == k:
            return out

No frequency can exceed len(nums), so the value range is bounded and you can index directly — a genuine $O(n)$ with no randomisation. Recognising a bounded range as licence to bucket is the transferable idea, and it is the same move as LC 274 H-Index.

Follow-ups: “Truly $O(n)$?” — bucket by frequency. “Ties?” — the problem guarantees uniqueness; LC 692 makes the tie-break lexicographic, which forces a custom key. “Streaming input?” — counts change over time, so you need a heap with lazy deletion, or a count-min sketch for approximate answers at scale.

LC 658 — Find K Closest Elements · Medium

Problem. Given a sorted array, an integer k and a value x, return the k closest elements to x, sorted ascending. Ties prefer the smaller element.

Constraints. 1 <= k <= len(arr) <= 10^4, arr sorted ascending, -10^4 <= arr[i], x <= 10^4.

Examples. arr = [1,2,3,4,5], k = 4, x = 3 gives [1,2,3,4] · arr = [1,2,3,4,5], k = 4, x = -1 gives [1,2,3,4]

pch.exerciseTag pch.exerciseTitle

Editorial

The crucial observation is that because the array is sorted, the k closest elements form a contiguous window. So instead of selecting k individual elements, you only need to locate one index: the window’s start.

Time $O(\log(n - k) + k)$ — the binary search plus the slice. Space $O(1)$ beyond the output.

The comparison x - arr[mid] > arr[mid + k] - x asks: “is the element I would drop from the left worse than the one I would gain on the right?” If so, slide right. Written this way — rather than with abs() — it also gets the tie rule right: on a tie the condition is false, hi = mid, and the window stays left, preferring smaller elements.

This is a genuine improvement over the heap approach. A size-k heap over all elements is $O(n \log k)$ and ignores the sortedness entirely; here the sortedness buys you $O(\log n)$.

([1,2,3,4,5], 4, -1) giving [1,2,3,4] is the out-of-range case: x sits below everything, so the leftmost window wins.

Follow-ups: “Do it with a heap?” — $O(n \log k)$; a valid answer that wastes the sortedness, and worth naming the contrast. “Two pointers from the middle?” — also $O(n)$: binary search for x, then expand outward comparing distances. “Unsorted input?” — then a heap or quickselect is the right tool.

LC 1481 — Least Number of Unique Integers after K Removals · Medium

Problem. Remove exactly k elements from the array to minimise the number of distinct integers remaining. Return that minimum.

Constraints. 1 <= len(arr) <= 10^5, 1 <= arr[i] <= 10^9, 0 <= k <= len(arr).

Examples. arr = [5,5,4], k = 1 gives 1 · arr = [4,3,1,1,3,3,2], k = 3 gives 2

pch.exerciseTag pch.exerciseTitle

Editorial

The greedy is rarest first, and the exchange argument is short: a distinct value only stops counting once all its occurrences are gone, so partial removals achieve nothing. Given a fixed budget, spending it on the cheapest complete eliminations maximises how many values disappear.

Time $O(n + m \log m)$ for m distinct values. Space $O(m)$.

The loop stops at the first group it cannot fully afford, and everything from there on survives — hence len(counts) - i. Reaching the end means the budget covered everything, so 0 remain; ([1], 1) is that case.

([1,2,3], 0) giving 3 is the zero-budget case: nothing is removed.

Because counts are bounded by len(arr), a bucket sort on the counts replaces the $O(m \log m)$ sort with $O(n)$ — the same bounded-range observation as LC 347 above. A min-heap of counts is a third equivalent route and the one that connects to this page.

Follow-ups: “Prove rarest-first is optimal” — the exchange argument; the likely question. ”$O(n)$?” — bucket the counts. “Maximise the distinct values remaining instead?” — remove from the most frequent, keeping one of each where possible. “What if removals were per-element costly?” — it becomes a knapsack.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

4 problems

0 easy4 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

• ○347Top K Frequent ElementsmediumCount with `Counter`, then heap on the counts (as above)NeetCode 150Blind 75amazonmetauberbytedance
• ○215Kth Largest Element in an ArraymediumThe exact size-$k$ min-heap template, or `heapq.nlargest`NeetCode 150LeetCode Top Interview 150
• ○451Sort Characters By FrequencymediumCount characters, then greedily emit from most to least frequent using a max-heap
• ○973K Closest Points to OriginmediumSame pattern, ranked by squared distance to the origin instead of raw valueNeetCode 150

Interview follow-ups

They ask	What they’re checking	The answer
“Why a min-heap for the k largest?”	Whether you understand the eviction, not the recipe	The root must be the element you want to discard, which is the smallest of the winners so far. It doubles as the answer to “kth largest” once the scan ends
“Why is it $O(n \log k)$ and not $O(n \log n)$?”	Precision about the bound	The heap never exceeds k, so each heap operation is $\log k$. And not every element pays it — in the eight-element trace, 3 of 8 were discarded on a single $O(1)$ comparison against the root
“Is the heap always better than sorting?”	Judgement over recall	No. At k = 5 of 200,000, nlargest beat sorted(...)[:k] by 13x; at k = n/2 the sort won by 4x, because $\log k$ approaches $\log n$ while the heap pays Python-level bookkeeping against Timsort’s C loop. The heap wins when k \ll n
“Now it is a stream and you cannot store the input”	Space, which is the real reason for the cap	The capped heap is the answer — $O(k)$ space, one pass, no random access. Sorting and quickselect both need the whole array, so both are out
“Give me the kth largest, not the top k”	Whether you notice the shortcut	return heap[0] — no final sort. Or quickselect at index n - k for $O(n)$ expected, if mutation is allowed and the data fits
“The values are bounded. Anything better?”	Reading the constraint	Counting or bucket sort: for LC 347, frequencies cannot exceed n, so index buckets by count and read down from n. A deterministic $O(n)$, no randomisation, and simpler code
“The array is sorted. Still a heap?”	Whether the pattern is applied blindly	No — binary search the insertion point and expand two pointers, $O(\log n + k)$. LC 658 is the trap; a heap works and throws the sortedness away
“How do you break ties?”	Care with the spec	Put the tiebreak in the sort key — a tuple (count, word), with care about which component needs negating. Absent a rule, note out loud that nlargest returns dictionary order, which the problem never promised
“heapreplace or heappushpop?”	Depth on the stdlib	heapreplace pops then pushes and needs a non-empty heap — correct after you have checked x > heap[0]. heappushpop pushes first, so it may return the element you just added — correct when you have not checked. Both are one operation rather than two, which is why they exist
“Can you do the top k in $O(n)$ worst case?”	Knowing the limits	Bucket sort if the keys are bounded. Otherwise median-of-medians quickselect gives deterministic $O(n)$ but with a constant factor bad enough that nobody uses it — name it, do not write it

Self-check

pch.quizTag pch.quizDefaultTitle

1. To find the k largest values you keep a min-heap. Why not a max-heap?

   A Python's heapq only provides min-heaps, so there is no choice B The root must be the element you want to evict -- the smallest of the winners so far. A max-heap puts the best element at the root, which is the one you never remove C A min-heap uses less memory for the same k D Because the answer must be returned in ascending order
   pch.quizShowAnswer

   B — The root must be the element you want to evict -- the smallest of the winners so far. A max-heap puts the best element at the root, which is the one you never remove — The root does double duty: it is the eviction candidate during the scan and the kth largest at the end. With a max-heap you would have to scan all k entries to find what to discard, turning O(n log k) into O(nk). The heap type is always the opposite of what you are hunting. heapq being min-only is a separate (real) inconvenience, handled by negating.

2. In the trace of [7, 2, 9, 4, 1, 8, 5, 3] with k = 3, three elements never entered the heap. What does that tell you about the bound?

   A The bound is really O(k log k), since only k elements matter B Not every element pays the log -- a discard is a single O(1) comparison against the root, and O(n log k) is the worst case C The bound is O(n) for random input D It means the heap was built lazily
   pch.quizShowAnswer

   B — Not every element pays the log -- a discard is a single O(1) comparison against the root, and O(n log k) is the worst case — Counted: 3 pushes, 2 replacements, 3 discards. Each discard compares against heap[0] and stops. The worst case for this loop is *ascending* input, where every element beats the root and all n pay O(log k) -- measured at 5 replacements for [1..8]. Descending input is the best case with zero replacements. Quote O(n log k); it is the ascending case.

3. For k = 100,000 out of n = 200,000, `sorted(a, reverse=True)[:k]` measured 4.2x faster than `heapq.nlargest(k, a)`. Why?

   A nlargest has a bug for large k B log k is nearly log n at that ratio, so the asymptotic advantage vanishes while the heap still pays per-element Python-level bookkeeping against Timsort's C loop C sorted uses multiple cores D Because the input was random rather than sorted
   pch.quizShowAnswer

   B — log k is nearly log n at that ratio, so the asymptotic advantage vanishes while the heap still pays per-element Python-level bookkeeping against Timsort's C loop — At k = n/2, log k = log n - 1: the theoretical saving is one comparison per element, and the constant factors swamp it. At k = 5 the same benchmark had nlargest ahead by 13.6x. "Use a heap for top k" is correct when k << n, which is what the phrasing usually implies -- and naming the crossover is a stronger answer than reciting the bound.

4. The problem says "find the k closest elements to x" and the input array is sorted. Is a size-k heap the right answer?

   A Yes -- "k closest" is the top-k cue B No -- binary search the insertion point then expand two pointers outward: O(log n + k) instead of O(n log k) C Yes, but only if k < log n D No -- use quickselect on the distances
   pch.quizShowAnswer

   B — No -- binary search the insertion point then expand two pointers outward: O(log n + k) instead of O(n log k) — LC 658, and the trap in this family. The heap solution works and is O(n log k), but it discards the sortedness entirely. For n = 10^5 and k = 10, the two-pointer expansion is about 27 operations against 10^5. Matching on the phrase "k closest" rather than on what structure the input actually has is the failure mode.

5. What is the difference between `heapq.heapreplace` and `heapq.heappushpop`?

   A They are aliases for the same operation B heapreplace pops then pushes (so it needs a non-empty heap and may return something larger than what you inserted); heappushpop pushes first, so it can immediately return the element you just added C heapreplace is O(log n) and heappushpop is O(n) D heappushpop maintains a maximum size automatically
   pch.quizShowAnswer

   B — heapreplace pops then pushes (so it needs a non-empty heap and may return something larger than what you inserted); heappushpop pushes first, so it can immediately return the element you just added — The order of operations decides which element can survive. After checking `x > heap[0]`, heapreplace is correct -- you know x belongs and the root does not. Without that check, heappushpop is correct: if x is smaller than everything, it comes straight back out. Both are a single sift rather than two, which is the reason they exist rather than push-then-pop.

6. LC 347 asks for the k most frequent elements. Why might bucket sort beat the heap?

   A Buckets use less memory B A frequency cannot exceed n, so you can index buckets by count and read down from n -- a deterministic O(n), better than O(n log k) and simpler C Because Counter is already sorted by frequency D It does not; the heap is optimal here
   pch.quizShowAnswer

   B — A frequency cannot exceed n, so you can index buckets by count and read down from n -- a deterministic O(n), better than O(n log k) and simpler — The bounded key is what unlocks it: build n + 1 buckets, drop each value into buckets[count], then walk from n downward taking values until you have k. No comparisons, no log, no randomisation. Checking whether a key is bounded before reaching for a heap is the habit worth building.

7. `top_k_frequent([1, 2, 3, 4], k=2)` -- every count is 1. What does `heapq.nlargest(2, counts, key=counts.get)` return, and what should you say about it?

   A [1, 2], and it is the correct canonical answer B [1, 2], which comes from dictionary insertion order -- not anything the problem specified. Either the statement gives a tiebreak rule that belongs in the sort key, or any valid answer is acceptable C It raises an error because the counts are tied D [4, 3], since nlargest prefers later elements on ties
   pch.quizShowAnswer

   B — [1, 2], which comes from dictionary insertion order -- not anything the problem specified. Either the statement gives a tiebreak rule that belongs in the sort key, or any valid answer is acceptable — The output is [1, 2], but nothing about the problem guarantees it -- it falls out of Python's insertion-ordered dicts. LC 692 does specify a tiebreak (lexicographic), which then has to go into the sort key, with care about which tuple component needs negating. Saying "any valid answer" out loud when there is no rule is the honest move.

8. The input is now a stream too large to store. Which approaches survive?

   A Sorting, since it can be done externally B The capped heap -- O(k) space, one pass, no random access. Sorting and quickselect both need the whole array C Quickselect, since it is O(n) expected D Bucket sort, since it is O(n)
   pch.quizShowAnswer

   B — The capped heap -- O(k) space, one pass, no random access. Sorting and quickselect both need the whole array — Bounded space is the real reason to cap the heap, and it is what LC 703 is built around. Quickselect mutates an array it must hold entirely; sorting needs all of it resident (external merge sort is a different algorithm with different assumptions). Bucket sort needs the value range up front and a bucket array, which may be fine -- but the capped heap needs neither.

Recall card

• Top k largest = min-heap capped at k. The root is the smallest winner, so it is both the eviction candidate and the kth largest at the end. Heap type is always the opposite of what you are hunting.
• The test is x > heap[0], then heapreplace. Comparing against anything else costs $O(nk)$.
• $O(n \log k)$ time, $O(k)$ space — and not every element pays the log: a discard is one comparison. Ascending input is the worst case, descending the best.
• heap[0] is the only meaningful slot. The heap is not sorted; sorted(heap, reverse=True) costs $O(k \log k)$ and only if the problem wants order.
• heapq is min-only. Negate for a max-heap, on the way in and out.
• heapreplace pops then pushes (needs a non-empty heap; correct after checking the root). heappushpop pushes first (correct when you have not checked).
• The heap wins when k \ll n. Measured: 13.6x faster than sorting at k = 5 of 200k, 4.2x slower at k = n/2. Name the crossover.
• Check for a bounded key first — LC 347’s counts are $\le n$, so bucket sort is a deterministic $O(n)$ and simpler.
• A sorted input is not a heap problem. LC 658: binary search then expand two pointers, $O(\log n + k)$.
• O(k) space is why it works on a stream. Sorting and quickselect both need the whole array.
• State the tiebreak or say any valid answer is fine — nlargest returns dictionary order, which the problem never promised.

Recap

• The top-k cue: whenever a problem only needs $k$ of $n$ elements, resist sorting everything.
• A min-heap capped at size $k$ tracks the top-$k$ largest in $O(n \log k)$ total, using only $O(k)$ extra space.
• heapq.nlargest / nsmallest give you the same pattern in one line, with an optional key= for ranking by a derived value.
• Quickselect trades the heap’s streaming ability for average-case $O(n)$, when you only need one $k$-th value from data already in memory.

Next: K-way Merge — the heap pattern for combining many sorted sequences into one.