Design a class that is constructed with k and an initial list of numbers, and whose add(val) inserts a value and returns the kth largest value seen so far.
Before you code
Keeping every value sorted makes each add O(n). You only ever need the kth largest, which is the smallest of the top k: the root of a min-heap that holds exactly the top k.
Hints
- Keep a min-heap of at most k values.
- On add, push the value; if the heap now has more than k values, pop the smallest.
- The answer is the heap's root,
heap[0].
Production & complexity notes
When solving Kth largest element in a stream on LeetCode (easy), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in The heap property in an array to reinforce the underlying pattern.
What it practices
A min-heap's root as a running threshold, from The heap property in an array.