Heaps and Priority Queues
Keeping only k candidates
The counterintuitive one: to track the k largest, keep a heap of the smallest of them.
Key idea
The inversion
To keep track of the k largest values seen so far, use a min-heap holding exactly those k values. The smallest of the k sits at the top, which is precisely the one that gets displaced when something better arrives.
That inversion is the thing to internalize. The heap's cheap operation should be the one you need most often, and here the frequent question is which of my keepers is the weakest.
Cost
Why this beats sorting
Each item costs one push and possibly one pop, on a heap of size k, so O(log k) each and O(n log k) overall. Space is O(k) rather than O(n).
Sorting everything is O(n log n) time and O(n) space. When k is small and n is large the difference is real, and when the data arrives as a stream that never ends, sorting is not even an option.
Why it works
Why it works on a stream
The invariant is that after processing any prefix of the input, the heap holds exactly the k largest values of that prefix.
It survives each step: adding one value makes k plus one candidates, and the true k largest of those are everything except the smallest, which is what gets popped. Nothing else can be discarded incorrectly, because anything already dropped was smaller than every current keeper.
That argument is what makes this correct without ever seeing the whole input, and it is the reason the technique fits problems that describe a stream of values arriving over time.
Gotcha
Push first, then trim
The order matters. Pushing and then popping if oversized is correct. Checking whether the new value beats the top before pushing also works but needs a separate branch for the case where the heap is not yet full.
Both appear in practice. The push-then-trim version has one code path and is harder to get wrong, so prefer it unless the extra push is measurably costly.
Tip
The kth largest is the top
Once the heap holds the k largest, its smallest element is the kth largest overall. So a design that must report the kth largest at any moment simply reads position 0.
That is the whole design for a class that accepts a stream and answers that question, which is the first problem below.
Key idea
The alternative worth naming
For a one-shot question on a fixed array, quickselect finds the kth largest in O(n) expected time by partitioning around a pivot and recursing into only the side that contains the answer.
It is faster in expectation than the heap and has an O(n squared) worst case unless the pivot is chosen carefully. Mention it as the alternative; the heap is easier to write correctly under time pressure and is usually the better interview answer.
Which heap for which question?
You must maintain the k smallest values from an ongoing stream. What kind of heap should hold them, and what sits at its top?
Kth Largest Element In A Stream
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.
Last Stone Weight
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.