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?

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.

The answer is the root, so the query is free

Notice the shape of what is being asked. There is a query after every arrival, so anything that costs work per query gets multiplied by the length of the stream. That pushes all the cost into maintenance and demands a structure whose answer is sitting in a known place.

A min-heap holding exactly the K largest values seen so far has that property. Its root is the smallest of those K, which is by definition the Kth largest overall. The query is a peek. Not a search, not a partial sort, a single read of a fixed slot.

Say that before writing anything. It reframes the problem from "how do I find the Kth largest" to "how do I maintain a set of K survivors", and the second is a much easier thing to reason about correctly.

The invariant, and where the discard happens

Each arrival costs one comparison against the root. If it is not larger than the root it cannot be in the top K, so it is dropped and nothing else happens. If it is larger, it displaces the root: the root is removed and the new value is inserted, and the heap is back at size K with a new smallest survivor.

// Min-heap capped at k: the root is the k-th largest, and is also the next value evicted.
private final PriorityQueue<Integer> survivors = new PriorityQueue<>();

void add(int value) {
    if (survivors.size() < k) {
        survivors.offer(value);
        return;                                   // still filling - no answer exists yet
    }
    if (value > survivors.peek()) {               // one comparison rejects the common case
        survivors.poll();
        survivors.offer(value);
    }
}

int kthLargest() {
    return survivors.peek();                      // O(1), no traversal
}

That guard does more than it appears to. It is the reason the structure is cheap in practice rather than only in the bound, and it is worth putting a number on.

What the cost is, derived

Take a stream of a billion values with K set to 100, arriving in no particular order. Every value pays one comparison against the root, so there are a billion comparisons no matter what. The interesting quantity is how many of them get past that guard.

A value enters the heap exactly when it is among the largest 100 of everything seen up to that point. For the i-th arrival in a randomly ordered stream that chance is 100 divided by i, so the expected number of entries is 100 times the sum of 1 over i from 101 to a billion, which is about 100 times the natural log of ten million. That is roughly 1,600 insertions out of a billion arrivals.

So the honest description is a billion cheap comparisons and about sixteen hundred heap operations of seven levels each. The heap is almost never touched. Anyone quoting O(n log K) without noticing this is quoting the worst case, which is real but requires a specific input: a stream in ascending order, where every single value beats the root and the log K factor is paid a billion times.

Space is O(K). That is the property the design exists for: a billion values were seen and a hundred were retained.

What you threw away, said out loud

The discard is irreversible. Being explicit about it is the difference between an answer and a solution.

Once rejected, a value is gone. That means the structure can answer for K and for anything smaller than K, by draining a copy of the heap in O(K log K), but it can never answer for K plus one. If the requirement later becomes the 150th largest, the stream has to be replayed, and a stream is usually the one thing that cannot be replayed.

Which makes the first question to the interviewer a real one rather than a formality. Is K fixed for the lifetime of the stream, or supplied with each query? If K varies without bound, the bounded heap is the wrong instrument and you want an order-statistic structure instead - a balanced search tree carrying subtree sizes, which answers for any rank in O(log n) but holds every distinct value, so memory grows with the stream. That trade is the whole design space, and naming both ends of it is the signal.

The version of this that catches people out is a query phrased as a percentile. The ninety-ninth percentile of a billion values is the ten-millionth largest, so K is a fixed fraction of n rather than a constant, and the heap holds ten million entries and is no longer bounded in any useful sense. That is where sketch structures for approximate quantiles belong, with a stated error bound in exchange for fixed memory.

The clarification nobody asks for

Does the Kth largest count repeated values? Given the stream 9, 9, 9 with K at three, the answer is 9 under the usual reading, because rank is positional. Under a distinct-values reading there is no third largest at all, and the same code returns 9 while answering the wrong question.

Both readings appear in real problem statements. Asking which one applies costs one sentence and is graded, because the two implementations differ: the distinct version needs a membership check before the heap is touched, and that check has to be against the retained set, which means it can only reject duplicates of values still held. A duplicate of something already discarded looks new. That subtlety is why the distinct variant is genuinely harder and not merely a filter bolted on the front.

Also settle what happens before K values have arrived. Returning the smallest so far, throwing, or returning a sentinel are all defensible; picking one silently is not.

Why the obvious alternatives lose

Keeping everything and sorting after each arrival is O(n log n) per query and O(n squared log n) over the stream. That is not a near miss.

Keeping a sorted array and inserting by binary search finds the position in O(log n) and then shifts elements, so the insert is O(n), and it holds every value. Quickselect finds the Kth largest of an array in expected linear time and is the right answer when you have the array, but it needs random access to all n values and reorders them, so it is disqualified by the word "stream" rather than by its bound.

Reaching for a max-heap is the classic misstep, and the reason is worth stating as a rule you can apply elsewhere. The heap holds what you are keeping, and its root has to be the next thing you are willing to lose. You are willing to lose the smallest survivor, so the root is a minimum.

The structure is chosen by the query, not by the words in the question: because the Kth largest is asked for after every arrival, the right answer is one that leaves it lying in a fixed place.

---

© 2026 Preptima. Originally published at preptima.com.