Kth Largest Element in a Stream
Part of Practice: Top-K Fundamentals
Design a class that tracks the k-th largest value in a growing stream of numbers. It is created with an integer k and an initial list nums, and it exposes one method: add(val) inserts a new number and returns the k-th largest number seen so far (duplicates count separately, so the 3rd largest of [5, 5, 4] is 4).
You may assume there are at least k numbers in the stream whenever add is called. Up to 10^4 calls to add can happen, and the initial list can hold up to 10^4 numbers, so recomputing from scratch on every call is too slow.
Examples
- Input:
- KthLargest(3, [4, 5, 8, 2]); add(3); add(5); add(10); add(9); add(4)
- Output:
- 4, 5, 5, 8, 8
After add(3) the stream is [4, 5, 8, 2, 3]; sorted descending it is [8, 5, 4, 3, 2], so the 3rd largest is 4. After add(10) the top three are [10, 8, 5], so the answer is 5.
- Input:
- KthLargest(1, []); add(-3); add(-2); add(-4); add(0)
- Output:
- -3, -2, -2, 0
With k = 1 the answer is simply the maximum seen so far.
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.