466. Kth Largest Element in a Stream
Design a class KthLargest that tracks the k-th largest value seen so far in a growing stream of integers — counted with duplicates, i.e. the k-th element in sorted (descending) order, not the k-th distinct value.
The constructor receives the integer k and an initial array nums (which may hold fewer than k elements, or none). Each call to add(val) appends one value to the stream and returns the current k-th largest element. It is guaranteed that whenever add is called, at least k values have accumulated, so the answer always exists.
The judge builds the object once, feeds it every value on the third input line in order, and compares the sequence of returned answers.
Example 1:
Input: KthLargest(3, [4, 5, 8, 2]); add(3), add(5), add(10), add(9), add(4)
Output: 4, 5, 5, 8, 8
Explanation: Start with [4, 5, 8, 2]. After add(3) the three largest are 8, 5, 4 → 4. After add(5): 8, 5, 5 → 5. After add(10): 10, 8, 5 → 5. After add(9): 10, 9, 8 → 8. After add(4): still 10, 9, 8 → 8.
Example 2:
Input: KthLargest(1, []); add(-3), add(-2), add(-4), add(0), add(4)
Output: -3, -2, -2, 0, 4
Explanation: k = 1 with an empty start simply tracks the running maximum: -3, then -2, still -2, then 0, then 4.
Constraints:
- 1 ≤ k ≤ 10⁴
- 0 ≤ nums.length ≤ 10⁴
- -10⁴ ≤ nums[i], val ≤ 10⁴
- At most 10⁴ calls to add.
- At least k values have been seen whenever add is called.
Hints:
Only the k largest values seen so far can ever matter — anything smaller than all of them can never climb into the top k, because values are only added, never removed.
Keep a min-heap holding exactly the k largest values. Its smallest element (the root) is then precisely the k-th largest of the whole stream.
On add: push the new value, and if the heap exceeds size k, pop the minimum once. The root is the answer — each add costs O(log k).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: KthLargest(3, [4, 5, 8, 2]); add(3), add(5), add(10), add(9), add(4)
Expected output: [4, 5, 5, 8, 8]