mediumCodingConceptMidSeniorStaff
Numbers arrive one at a time and after each one you must answer what the Kth largest so far is. What do you keep, and what do you deliberately throw away?
Keep a min-heap holding exactly the K largest values seen. Its root is the answer, so the query is a read rather than a search, and every value smaller than that root is discarded the moment it arrives. What you give up is the ability to answer for any K larger than the one you chose, which is why the first thing to establish is whether K is fixed.
6 min readUpdated 2026-08-15
Answer
Short answer
Keep a min-heap of size k containing the k largest values seen so far. The heap root is the kth largest value, so each query is an O(1) peek after O(log k) maintenance on arrivals that enter the heap. Values smaller than the root can be discarded because they can no longer affect the fixed-k answer.
Was this answer helpful?
Likely follow-ups
- The query changes to the ninety-ninth percentile so far. Why does your structure stop being bounded, and what replaces it?
- Values can also be retracted from the stream. What does that do to the discarding argument?
- Two machines each see half the stream. What must they exchange to answer for the whole of it?
- K is fixed at ten but the stream is a hundred values long. Is the heap still the answer you would write?
Related questions
- You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?mediumAlso on heaps and priority-queue6 min
- Return the k most frequent elements from a large stream of values. Why not just sort by frequency?mediumAlso on heaps and priority-queue4 min
- Numbers arrive one at a time and after each one I want the running median. How would you keep it?mediumAlso on heaps and priority-queue5 min
- Find the cheapest route between two nodes in a weighted directed graph. Then tell me what breaks if one edge has a negative weight.mediumAlso on priority-queue5 min