Kth Largest Element in a Stream: Maintain the Cutoff
Maintain the kth largest value after every streamed add with a size-k min-heap, JavaScript code, walkthrough, complexity, and pitfalls.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Kth Largest Element in a Stream is the online form of a familiar selection problem. Numbers arrive over time, and after every add(value) call we must report the kth largest number seen so far. Re-sorting all historical values on every call works, but it wastes the fact that consecutive answers differ by only one new number.
The visualizer maintains a size-k min-heap across the constructor's seed values and every later addition. The heap stores the current top k values, not the entire stream. Its root is the smallest of those winners, which makes it the current kth largest value.
The problem is online, not one-shot
Design a class with two operations:
- Initialize it with
kand an initial arraynums. - Call
add(val)repeatedly; each call insertsvaland returns the current kth largest element.
For k = 3, nums = [4, 5, 8, 2], and additions [3, 5, 10, 9, 4], the answers are [4, 5, 5, 8, 8].
The constructor is not special mathematically. It simply feeds each seed value through the same retention rule that add uses. That gives one invariant for the whole lifetime of the object rather than separate initialization and update logic.
The bounded min-heap invariant
Maintain a min-heap with no more than k values. After every processed value—whether it came from nums or add—the heap contains the largest min(k, seen) values observed so far.
The update procedure is deliberately short:
- Insert the incoming value.
- If heap size exceeds
k, remove the minimum. - Return the root.
When the heap is full, its root is the boundary separating retained winners from values that are too small to matter. A newly added small number may enter briefly and then be immediately removed. That is still correct: it cannot enter the top k while there are already k values greater than or equal to it.
The root is not the largest item in the heap. It is the smallest among the k largest seen values, so it is exactly the kth largest in the full stream.
Canonical JavaScript solution
The visualizer's source code uses MinPriorityQueue. Priority queue libraries vary on whether front, peek, enqueue, or push are the method names, but the data-structure behavior is identical.
var KthLargest = function(k, nums) {
this.heap = new MinPriorityQueue();
this.k = k;
for (let i = 0; i < nums.length; i++) {
this.add(nums[i]);
}
};
KthLargest.prototype.add = function(val) {
this.heap.enqueue(val);
if (this.heap.size() > this.k) {
this.heap.dequeue();
}
return this.heap.front();
};There is no need to sort the heap after each update. A binary min-heap keeps only a partial order: every parent is no greater than its children. Insertion sifts a value upward, and removing the root sifts a replacement downward. Both changes cost O(log k) because the heap is capped.
Walkthrough: the canonical stream
Start with k = 3 and seed nums = [4, 5, 8, 2]. Treat the heap displays as sorted sets for readability; a physical heap may arrange non-root nodes differently.
| Value processed | Heap after trim | Reason |
|---|---|---|
seed 4 | [4] | Under capacity |
seed 5 | [4, 5] | Under capacity |
seed 8 | [4, 5, 8] | Three current winners |
seed 2 | [4, 5, 8] | Insert then evict 2 |
At this point the root is 4: among [8, 5, 4], it is third largest. Now process the stream.
add(val) | Temporary heap | Removed | Returned root |
|---|---|---|---|
add(3) | [3, 4, 5, 8] | 3 | 4 |
add(5) | [4, 5, 5, 8] | 4 | 5 |
add(10) | [5, 5, 8, 10] | 5 | 5 |
add(9) | [5, 8, 9, 10] | 5 | 8 |
add(4) | [4, 8, 9, 10] | 4 | 8 |
The returned sequence is 4, 5, 5, 8, 8. The second 5 matters: values are ranked by occurrences, so duplicate values can occupy multiple top positions. On add(4) at the end, 4 cannot improve the top three, so it is evicted immediately and the cutoff stays 8.
What if fewer than k values exist?
The visualizer supports an empty or undersized seed array. Before k total values have arrived, the heap is simply under capacity. Its root is the minimum among all values received so far.
Some problem statements guarantee enough initial values or evaluate add only after the kth value exists. If your own API must support earlier calls, define that contract explicitly: return undefined, null, or an optional result until seen >= k. Do not pretend a first or second value is already the fourth largest. The core heap update remains the same; only the public return policy changes.
Why not store the entire stream?
If we retained every value, each add could append to an array and sort all values again: O(m log m) for a stream of length m at that moment. Repeating that work is costly as the stream grows.
A max-heap containing every value could report the maximum quickly, but finding the kth largest would require extracting k - 1 elements or maintaining additional state; it also uses O(m) memory. The size-k min-heap keeps only the values that can currently affect the answer. Historical losers are discarded permanently.
Complexity
| Operation | Time | Space impact |
|---|---|---|
Constructor over n seed values | O(n log k) | Heap remains O(k) |
add(val) | O(log k) | At most one temporary extra entry |
| Read returned root | O(1) | None |
The add method performs at most one insertion and one remove-min. The heap has height O(log k), not O(log total stream length), because its capacity is fixed. This is the important difference between a priority queue that stores every observation and a bounded priority queue that stores only candidates.
For k = 1, the object acts as a running maximum: every non-maximum addition is immediately evicted. For a very large k relative to observations, it simply accumulates values until it reaches capacity.
Common mistakes
- Recreating the heap inside every
addcall. The class must preserve state across the stream. - Sorting all values on every update instead of preserving the previous top-
kwork. - Using a max-heap and removing its root on overflow, which removes the best value.
- Forgetting that initial
numsmust be processed under the same size cap. - Assuming a heap's internal array is sorted beyond its root property.
- Ignoring an undersized-stream contract when calls can happen before
kvalues have been seen.
Related heap patterns
The one-shot version, Kth Largest Element in an Array, applies the same invariant to a finite input. Top K Frequent Elements uses a size-k min-heap too, but changes the comparison key from numeric value to frequency. For the mechanics behind each enqueue and dequeue, see Min-Heap Operations.
Step through Kth Largest Element in a Stream interactively to watch seed values, stream additions, evictions, and emitted answers.
FAQ
Why does the min-heap root represent the kth largest value?
The heap stores exactly the largest k values seen so far. Its root is the smallest member of that retained set, leaving exactly k - 1 retained values above it. All discarded values are no larger than that cutoff.
Is add always O(log k), even when the new value is tiny?
With the simple push-then-pop implementation, yes: it may perform a heap insertion and immediate removal, each bounded by O(log k). An implementation can first compare a full heap's root with the new value and skip it when it cannot win, but the asymptotic bound stays O(log k) and the simple form is less error-prone.
Can the constructor call add for each initial number?
Yes, and it is a clean design. It applies exactly the same retention rule to seed values and later values, guaranteeing the heap has the correct state before the first external add call.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.