Kth Largest in a Stream: Keep the Useful Values in TypeScript

Finding the third‑largest value once is fairly straightforward: sort the values and read the third position. Now imagine being asked again after every new arrival. Keeping the entire history sorted starts to feel like tidying the whole kitchen each time somebody puts down a teaspoon.
LeetCode's Kth Largest Element in a Stream problem asks for that repeated answer. We initialise a class with a rank and some values, then return the current kth largest after each addition. My approach keeps only the best k occurrences in a min‑heap. Its smallest retained value is exactly the answer we need.
A Rank Counts Occurrences
This is the kth position in descending sorted order, not the kth distinct value. With [8, 7, 7, 3] and k = 3, the answer is 7. Removing duplicates would change the question.
The challenge allows an initial array of up to 10,000 values, with 1 <= k <= nums.length + 1. Values lie between ‑10,000 and 10,000, and there may be up to 10,000 calls to add. The initial array may contain one fewer value than the requested rank. After the first addition, there are enough values for the answer to exist.
That last detail is easy to miss. An empty initial array is legal when k = 1. A constructor does not need to produce a ranked answer, so it can hold an incomplete collection until the first call. I keep ingestion separate from the public add method to make that distinction visible.
Why a Min‑Heap Helps
In my quickselect walkthrough, the task is to find one rank in a finished array. Repeating that selection over an ever‑growing history would revisit values we could already have discarded. A stream lets us maintain the information needed for the next answer instead.
Suppose the heap already contains the largest k values seen so far. Its root is the smallest of those retained values, so it sits at the cutoff. A new value below that cutoff cannot enter the top group. A larger value replaces the root, after which we repair the heap.
An equal value can also be ignored once the heap is full: exchanging one occurrence for an equal occurrence cannot change the kth value. Before the heap reaches size k, however, every occurrence must be stored, including duplicates. We haven't filled all the ranked positions yet.
This gives an induction argument. An empty retained collection is correct. Adding a value to an incomplete collection preserves every value seen so far. Once full, either the new value cannot improve the retained group, or replacing its smallest member restores the largest k. The invariant therefore survives every arrival.
A Heap is Only Partly Ordered
A min‑heap guarantees that each parent is no larger than its children. It does not guarantee that reading its backing array from left to right produces sorted values. The root is cheap to inspect precisely because we maintain less order than a complete sort requires.
For a zero‑based array, a node's children sit at 2 * index + 1 and 2 * index + 2. A newly appended value may need to move upwards. Replacing the root with a larger value may require movement downwards, always swapping with the smaller available child so the parent rule survives on both sides.
The Complete TypeScript Class
The constructor checks the rank relationship, then feeds the initial values through the same private retention method used by add. It reads the supplied array without sorting or modifying it. Negative values and repeated values require no special branches.
export class KthLargest {
private readonly heap: number[] = [];
public constructor(private readonly k: number, nums: readonly number[]) {
if (!Number.isInteger(k) || k < 1 || k > nums.length + 1) {
throw new RangeError('k must be between 1 and nums.length + 1.');
}
for (const value of nums) this.retain(value);
}
public add = (value: number): number => {
this.retain(value);
return this.heap[0]!;
};
private retain = (value: number): void => {
if (this.heap.length < this.k) {
this.heap.push(value);
this.bubbleUp(this.heap.length - 1);
} else if (value > this.heap[0]!) {
this.heap[0] = value;
this.bubbleDown();
}
};
private bubbleUp = (start: number): void => {
let child = start;
while (child > 0) {
const parent = Math.floor((child - 1) / 2);
if (this.heap[parent]! <= this.heap[child]!) break;
[this.heap[parent], this.heap[child]] = [
this.heap[child]!, this.heap[parent]!,
];
child = parent;
}
};
private bubbleDown = (): void => {
let parent = 0;
while (true) {
const left = parent * 2 + 1;
if (left >= this.heap.length) return;
const right = left + 1;
const smaller = right < this.heap.length && this.heap[right]! < this.heap[left]!
? right : left;
if (this.heap[parent]! <= this.heap[smaller]!) return;
[this.heap[parent], this.heap[smaller]] = [
this.heap[smaller]!, this.heap[parent]!,
];
parent = smaller;
}
};
}The non‑null assertions describe positions already established by the surrounding checks: a child and its parent exist during upward repair, and downward repair checks for a left child before reading either candidate. The public return is safe because the constructor permits at most one missing ranked position, and add supplies that value before reading the root.
Watch the Cutoff Change
Start with k = 3 and [4, 5, 8, 2]. The retained values are 4, 5, and 8. The 2 cannot improve that group. The root is 4, which is the third‑largest value so far.
Adding 3 leaves the answer at 4. Adding another 5 replaces the 4, leaving the occurrences 5, 5, and 8, so the answer becomes 5. Both fives count. Adding 10 leaves 5, 8, and 10, and the answer is still 5. Adding 9 leaves 8, 9, and 10, raising the answer to 8. A later 4 cannot change it.
Those are retained values written in sorted order to explain the rank, not a promise about the heap array's layout. In the downloadable trace, I print the physical heap order beside a separately sorted copy so that distinction stays visible.
For k = 1, the same code keeps only the largest value. There is never a second heap level to repair. At the other extreme, if the constructor starts with exactly k - 1 values, the first addition fills the last place before returning the smallest retained value.
Costs Depend on the Retained Group
An accepted addition moves through at most the heap's height, giving O(log k) repair work for k >= 2. Rejected values only need the root comparison. A bound covering k = 1 as well is O(log(k + 1)) per addition, using ordinary indexed‑array operations and amortised append cost.
With n initial values, this constructor takes O(n log(k + 1)) time because it feeds them in one by one. A different implementation could use a bottom‑up heap construction for its initial retained group; that is not what this code does. The heap stores at most k numbers, giving O(k) additional space independently of how long the stream continues.
Discarding values is safe only because arrivals never disappear and k stays fixed. A sliding time window needs to expire old values; changing the requested rank may need values we threw away. I would not stretch this little class into either problem without reconsidering the stored information.
Check Answers After Every Arrival
My reference implementation stores the complete history, sorts a fresh copy after each addition, and reads position k - 1. It is intentionally less efficient and easier to inspect. The heap's answer must agree after every operation, not just after the final value.
The checks exhaust small initial arrays and three‑value addition sequences over ‑1, 0, and 1, trying every permitted rank. That naturally exercises duplicate occurrences and initially incomplete heaps. Seeded sequences cover more values, and separate cases check the maximum initial length, the largest permitted rank, and 10,000 additions. Frozen initial arrays confirm that construction doesn't mutate callers' data.
My stateful data structures lab contains these checks and an editable stream trace. Try changing the comparison to retain only distinct values, or swapping with the larger child during downward repair. Seeing the first incorrect answer is more instructive than staring at a heap that happens to end up looking plausible.
The same bounded‑selection idea appears in my Top K Frequent Elements article, where the heap ranks frequency records. Here, the values themselves supply the ranking. In both cases, keeping the cutoff available saves us from maintaining a complete order we never needed.
Downloadable Resource
Stateful Data Structures Lab
Use my TypeScript lab to follow circular‑queue wraparound and a bounded min‑heap across complete operation sequences. Compare both structures with independent array and sorted references, inspect their internal state, and experiment with rejected queue operations, duplicate ranks, and heap repairs.